How Often Each Prefix Appears

Difficulty: 1700 6000 ms 128 MB

strings kmp

For each prefix length k (1..|S|), print how many times that prefix occurs as a substring of S.

Input: one line with the string S.

Output: |S| integers: the occurrence count of each prefix.

Constraints:

• 1 ≤ |S| ≤ 10⁵
• lowercase letters

Sample Tests

aba

2 1 1

aaaa

4 3 2 1

Read the Editorial