Tổng mảng hàm tiền tố
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Với xâu $S$ độ dài $n$ (đánh số từ $0$), hàm tiền tố $\pi[i]$ được định nghĩa là độ dài lớn nhất của tiền tố thực sự của $S[0..i]$ mà đồng thời cũng là hậu tố của $S[0..i]$. Hãy tính tổng $\sum_{i=0}^{n-1} \pi[i]$.
Dữ liệu vào
Một dòng duy nhất chứa xâu $S$ gồm các chữ cái thường.
Dữ liệu ra
In ra một số nguyên là tổng giá trị hàm tiền tố của $S$.
Ví dụ
| Input | Output |
|---|---|
| aabaaab | 9 |
Giới hạn
- $1 \le |S| \le 10^5$
Community Discussion