Đếm Xâu Con Lũy Thừa

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

Một xâu $W$ được gọi là xâu lũy thừa nếu tồn tại một xâu $X$ khác rỗng và một số nguyên $k \ge 2$ sao cho $W$ chính là xâu $X$ lặp lại $k$ lần liên tiếp ($W = \underbrace{X + X + \dots + X}_{k\text{ lần}}$).

Cho xâu $S$ độ dài $n$. Hãy đếm số cặp chỉ số $(i, j)$ với $0 \le i < j < n$ sao cho xâu con $S[i..j]$ là một xâu lũy thừa.

Dữ liệu vào
  • Một dòng duy nhất chứa xâu $S$ ($1 \le |S| \le 3000$).
Dữ liệu ra
  • Một số nguyên duy nhất là số cặp $(i, j)$ thỏa mãn.
Ví dụ
Input Output
aaaa 6
abab 1
Giới hạn
  • $1 \le |S| \le 3000$, chỉ gồm các chữ cái 'a'–'z'.
Draft saved