Problem statement: You are given a string s of length n. Compute the Z-function — an array z of length n, where z[i] is the maximum length of a substring starting at position i that matches a prefix of the string.

Input format:
The first line is the integer n (1 ≤ n ≤ 1 000 000).
The second line is the string s itself, of length n (Latin letters, no spaces).

Output format: n numbers z[0] … z[n-1], separated by spaces (usually z[0] = 0).

Solution: We maintain a window [l…r] in which a match with the prefix has already been found. For each position i we first take z[i] = min(r - i + 1, z[i-l]) when i ≤ r, so that already known characters are not re-checked. We then extend the match by comparing further characters naively. If the new right boundary exceeds r, we shift l, r.
As a result the algorithm runs in linear time and O(n) memory.

Once the loop finishes, z holds every value of the Z-function.

For example,

gives

Proof of correctness: Invariant: before processing i, the window [l…r] genuinely reflects the longest prefix match ending no earlier than r. When i≤r, the value z[i-l] is the match length at the mirrored position, and we use no more than what is guaranteed up to r. The subsequent naive extension fully checks the remaining characters. For i>r we start comparing from scratch, which is correct. Thus every z[i] is computed without gaps or redundant checks.