Đếm Xâu Con Lũy Thừa
Points
85
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Đề 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'.
Community Discussion