1820. Each Prefix of the Word, Counted in the Text
Given a word w of length m and a text t of length n, print for every k from
1 to m how many times w[0..k-1] occurs in t.
Occurrences may OVERLAP, and counts are wanted, one per prefix length.
w = aa, t = aaaa -> 4 3
w = abc, t = xabcyabc -> 2 2 2
w = ana, t = banana -> 3 2 2
w = abcd, t = abc -> 1 1 1 0
w = abc, t = xyzxyz -> 0 0 0
The first example is the shape of the problem: a occurs 4 times and aa
occurs 3 times, at positions 0, 1 and 2, all overlapping. A counter that jumps
forward by k after a match reports 4 2, which was confirmed by running it.
Note the fourth example: a prefix can occur even when the whole word does not, so the counts are not all equal and not necessarily decreasing to zero at once.
## What most people try first
Search t separately for each of the m prefixes. Each search is O(n + k)
even done well, so the total is O(n m): about 4 * 10^10 at
n = m = 200000. The method below is one prefix function and two sweeps, about
1.2 * 10^6 steps.
## One table, then push the counts down the chain
g = w + '#' + t
pi = prefix function of g
cnt[0..m] = 0
for i in m+1 .. |g|-1: cnt[pi[i]] += 1
for k in m down to 1: cnt[pi[k-1]] += cnt[k]
print cnt[1], cnt[2], ..., cnt[m]
The first loop runs over the TEXT part only, recording at each text position the
longest prefix of w ending there. The second loop pushes those counts down the
border chain of w itself, so a shorter prefix inherits every occurrence of
every longer prefix that contains it.
## Why the chain push is exactly right
At text position i, the prefixes of w that end there are exactly the border
lengths of g[0..i], which problem 1805 showed is the chain pi[i],
pi[pi[i]-1], and so on. Because the separator caps every value at m, that
whole chain lies inside the word.
The second loop walks k downwards, so when cnt[k] is read every count that
belongs to it has already arrived from larger indices. Each occurrence is
therefore delivered to every shorter link exactly once, and never twice.
## Why there is no plus one here
Problem 1808 asks the same question about a string and ITSELF, and there each
prefix has one extra occurrence at position 0 that the table never reports. Here
the word and the text are separate strings, the first loop skips the word
entirely by starting at m + 1, and no occurrence is missing. Carrying the
+ 1 across from 1808 adds a phantom occurrence to every answer.
## Magnitude
Each count is at most n, which is 2 * 10^5, so every value fits in a signed
32 bit integer many times over. Nothing overflows.
## Cost
O(n + m) time and memory.
Constraints - `1 ≤ length of w ≤ 200000` - `1 ≤ length of t ≤ 200000` - both strings contain only lowercase English letters - the word may be longer than the text, in which case its longer prefixes have count 0
Input
The first line contains the word w.
The second line contains the text t. Both are lowercase English letters.
Output
Print m integers on one line separated by single spaces, where m is the length of the word. The k-th of them, counting from 1, is how many times the first k characters of the word occur in the text, counting overlapping occurrences.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.