Problem statement: You are given a string s of length n. Compute the prefix function — an array p of length n, where p[i] is the length of the longest proper prefix of the substring s[0…i] that is also its suffix.

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 p[0] … p[n-1], separated by spaces (as a rule p[0] = 0).

Solution: We keep a variable k — the value of p[i-1]. For position i we walk up the links by setting k ← p[k-1] until the characters s[i] and s[k] match or k = 0. On a match we increment k++ and store p[i] = k. The algorithm traverses the string once, with O(n) time and O(n) memory.

After the loop the array p holds the prefix function.

For example,

gives

Proof of correctness (sketch): Invariant: before position i is processed, the variable k equals p[i-1]. The while loop guarantees that on exit k is the length of the longest proper prefix matching a suffix of s[0…i-1] that can still be extended by the character s[i]. If the extension is possible we add 1; otherwise p[i]=0. Consequently every p[i] is correct, and the work is linear because k only decreases inside the loop.