Tần Suất Mọi Tiền Tố

Buổi 54 — KMP & Z-function Dynamic Programming
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Submissions
Đề 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'.
Draft saved