Tần Suất Mọi Tiền Tố
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Đề bài
Cho xâu $S$ độ dài $n$. Với mỗi $i$ từ $1$ đến $n$, hãy đếm xem tiền tố độ dài $i$ của $S$ (tức $S[0..i-1]$) xuất hiện bao nhiêu lần như một xâu con liên tiếp trong $S$.
Dữ liệu vào
- Một dòng duy nhất chứa xâu $S$ ($1 \le |S| \le 10^6$).
Dữ liệu ra
- Gồm $n$ số nguyên cách nhau bởi dấu cách, số thứ $i$ là số lần xuất hiện của tiền tố độ dài $i$ trong $S$.
Ví dụ
| Input | Output |
|---|---|
| abab | 2 2 1 1 |
| aaaa | 4 3 2 1 |
Giới hạn
- $1 \le |S| \le 10^6$, chỉ gồm các chữ cái
'a'–'z'.
Community Discussion