Cấu Trúc A + B + A

Buổi 54 — KMP & Z-function Dynamic Programming
Points
100
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Submissions
Đề bài

Cho số nguyên dương $K$ và xâu $S$ độ dài $n$. Hãy đếm số lượng cặp chỉ số $(i, j)$ với $0 \le i \le j < n$ sao cho xâu con $S[i..j]$ có thể biểu diễn dưới dạng $A + B + A$, trong đó:

  • $A$ là xâu có độ dài $|A| \ge K$.
  • $B$ là xâu khác rỗng ($|B| \ge 1$).
Dữ liệu vào
  • Dòng 1: số nguyên dương $K$ ($1 \le K \le 3000$).
  • Dòng 2: xâu $S$ ($1 \le |S| \le 3000$).
Dữ liệu ra
  • Một số nguyên duy nhất là số lượng xâu con thỏa mãn.
Ví dụ
Input Output
1\nababa 4
2\nabcabcabc 8
Giới hạn
  • $1 \le K \le 3000$, $1 \le |S| \le 3000$, chỉ gồm các chữ cái 'a'–'z'.
Draft saved