1808. How Often Each Prefix Appears In the Word Itself
For every k from 1 to n, print how many times the prefix s[0..k-1] occurs
inside s.
Occurrences may OVERLAP, and counts are wanted, one per prefix length.
aaaa -> 4 3 2 1
abacaba -> 4 2 2 1 1 1 1
aabaabaab -> 6 3 3 2 2 2 1 1 1
abcdef -> 1 1 1 1 1 1
Read aaaa. The prefix a occurs 4 times, aa occurs 3 times at positions 0,
1 and 2, all overlapping, aaa twice and the whole string once.
Read aabaabaab. The prefix aabaab of length 6 occurs twice, at 0 and at 3,
and those two copies share three characters.
## What most people try first
For each k, scan the string and compare. That is O(n^2) character
comparisons; at n = 200000 it is about 2 * 10^10. The method below costs
about 6 * 10^5.
A subtler wrong version counts each prefix by jumping forward k after a match.
On aaaa it prints 4 2 1 1 instead of 4 3 2 1, and on aabaabaab it prints
6 3 3 1 1 1 1 1 1. Both were confirmed by running it.
## Count endings, then push them down the chain
Every occurrence of a prefix ENDS somewhere. At position i, the prefix of
length pi[i] ends there, and so does every prefix on the chain below it.
cnt[k] = 0 for all k
for i in 0 .. n-1: cnt[pi[i]] += 1
for i in n-1 down to 1: cnt[pi[i-1]] += cnt[i]
answer for k is cnt[k] + 1
The first loop records, for each position, the LONGEST prefix ending there. The
second pushes each count down to the next link of the chain, so a prefix
inherits every occurrence of every longer prefix that contains it. The final
+ 1 is the occurrence of each prefix at position 0, which the loops never see
because pi only ever reports PROPER borders.
## Why pushing down the chain is exactly right
The prefix of length k ends at i exactly when k is pi[i] or somewhere on
the chain pi[i], pi[pi[i]-1], and so on, which problem 1805 showed is the
complete set of borders of s[0..i]. Adding cnt[i] into cnt[pi[i-1]] while
sweeping i downwards therefore delivers each count to every shorter link
exactly once, because the values at larger i are already final when they are
passed on.
## Magnitude
Each count is at most n, so 2 * 10^5, and every value fits in a signed 32
bit integer with room to spare. Nothing here overflows.
## Cost
O(n) time and O(n) memory.
Constraints - `1 ≤ length of s ≤ 200000` - `s` contains only lowercase English letters - occurrences may overlap
Input
A single line containing the string s, of lowercase English letters.
Output
Print n integers on one line separated by single spaces. The k-th of them, counting from 1, is how many times the prefix of length k occurs in s, counting overlapping occurrences.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.