1815. How Far Each Place Agrees With the Beginning
For a string s of length n, the Z ARRAY holds, at index i, the length of the
longest run starting at i that matches the beginning of s character for
character. By convention z[0] is n.
Print the whole array.
aaaaa -> 5 4 3 2 1
abcabcd -> 7 0 0 3 0 0 0
aabaabaab -> 9 1 0 6 1 0 3 1 0
abcdef -> 6 0 0 0 0 0
Read aabaabaab. At i = 3 the rest of the string is aabaab, six characters,
and the string begins with aabaab, so z[3] is 6. Those six characters
OVERLAP the prefix they are being compared against, which is allowed: the
question is only whether the characters agree.
The prefix function of problem 1801 answers a question about what ENDS at a position. The Z array answers one about what STARTS there. They carry the same information and neither is derivable from the other by a one-line formula.
## What most people try first
At each i, walk forward while the characters agree. On 200000 identical
characters every walk runs to the end, giving about 2 * 10^10 comparisons. The
method below does about 4 * 10^5.
## Remember the window you already matched
Keep the interval [l, r) of the rightmost match found so far, meaning
s[l..r-1] equals s[0..r-l-1].
l = r = 0
for i in 1 .. n-1:
if i < r: z[i] = min(r - i, z[i - l])
while i + z[i] < n and s[z[i]] == s[i + z[i]]: z[i] = z[i] + 1
if i + z[i] > r: l = i; r = i + z[i]
## Why the min is there and what happens without it
Inside the window, s[i] onwards is a copy of s[i-l] onwards, so z[i-l] is
a free starting guess. But that copy is only known to be valid up to r, so the
guess must be capped at r - i. Copying z[i-l] uncapped claims agreement about
characters past r that were never compared.
On aabaabaab the uncapped version prints 9 1 0 6 1 0 6 1 0, claiming a
six-character agreement at position 6 where only three characters remain. That
was confirmed by running it.
## Why it is linear
r never decreases, and the while loop only ever runs when it is about to
push r further right. Each character of s can be the one that moves r at
most once, so the total work in the while loops over the whole run is at most
n.
## Cost
O(n) time and O(n) memory.
Constraints - `1 ≤ length of s ≤ 200000` - `s` contains only lowercase English letters - `z[0]` is defined to be the length of `s`
Input
A single line containing the string s, of lowercase English letters.
Output
Print the n values of the Z array on one line, separated by single spaces, in index order from 0. The first value is the length of s itself.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.