Truy Vấn Đếm Palindrome Trong Đoạn

Buổi 53 — String Hashing prefix-sum
Points
85
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
string
Submissions
Đề bài

Cho chuỗi $S$ gồm $N$ ký tự in thường và $Q$ truy vấn. Mỗi truy vấn gồm hai số nguyên $L$ và $R$ ($1$-indexed), hãy đếm số lượng chuỗi con đối xứng (palindrome) nằm hoàn toàn trong đoạn $S[L..R]$.

Hai chuỗi con ở vị trí khác nhau được tính là khác nhau.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $Q$.
  • Dòng thứ hai chứa chuỗi $S$ có độ dài $N$.
  • $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $L$ và $R$.
Dữ liệu ra
  • Với mỗi truy vấn, in ra số lượng chuỗi con đối xứng trong đoạn $S[L..R]$.
Ví dụ
Input Output
5 3\nabcba\n1 5\n1 3\n2 4 7\n4\n4
Giới hạn
  • $1 \le N \le 3000$
  • $1 \le Q \le 10^5$
  • $1 \le L \le R \le N$
  • Chuỗi chỉ chứa ký tự in thường từ a đến z.

Giải thích ví dụ 1: Truy vấn 1 ($S[1..5] = $ abcba): palindromes là a, b, c, b, a, bcb, abcba → 7.

Draft saved