Tổng mảng Z
Points
40
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$), mảng $Z$ được định nghĩa với $Z[0] = 0$ và với mọi $i \ge 1$, $Z[i]$ là độ dài tiền tố chung dài nhất (LCP) giữa $S$ và hậu tố $S[i..n-1]$. Hãy tính tổng $\sum_{i=0}^{n-1} Z[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 các phần tử của mảng $Z$.
Ví dụ
| Input | Output |
|---|---|
| abacaba | 5 |
Giới hạn
- $1 \le |S| \le 10^5$
Community Discussion