Tổng Tiền Tố Chung Của Mọi Cặp Hậu Tố
Points
55
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
string
Đề bài
Cho một xâu $S$ độ dài $N$ chỉ gồm các chữ cái tiếng Anh in thường, đánh chỉ số từ $0$ đến $N-1$. Với mỗi vị trí $i$, gọi $S[i..]$ là hậu tố bắt đầu từ vị trí $i$ đến hết xâu $S$. Gọi $\text{LCP}(S[i..], S[j..])$ là độ dài tiền tố chung dài nhất của hai hậu tố $S[i..]$ và $S[j..]$. Hãy tính tổng độ dài tiền tố chung dài nhất trên tất cả các cặp hậu tố phân biệt: \[\sum_{0 \le i < j < N} \text{LCP}(S[i..], S[j..])\]
Dữ liệu vào
Một dòng duy nhất chứa xâu $S$ ($2 \le |S| \le 10^5$) chỉ gồm các chữ cái in thường từ 'a' đến 'z'.
Dữ liệu ra
In ra một số nguyên duy nhất là tổng tìm được.
Ví dụ
| Input | Output |
|---|---|
| ababa | 7 |
Giới hạn
Thời gian: 1.0s, Bộ nhớ: 256MB.
Community Discussion