1801. The Table That Makes Searching Linear
For a string s of length n, the PREFIX FUNCTION pi is an array of n numbers.
pi[i] is the length of the longest string that is both a PROPER prefix of
s[0..i] and a suffix of s[0..i]. Proper means it cannot be the whole of
s[0..i], so pi[0] is always 0.
Print the whole array.
abcabcd -> 0 0 0 1 2 3 0
aaaa -> 0 1 2 3
aabaabaab -> 0 1 0 1 2 3 4 5 6
Read abcabcd. At i = 5 the prefix so far is abcabc, whose first three and
last three characters are both abc, so pi[5] is 3. At i = 6 the prefix is
abcabcd, which ends in d and starts with a, so nothing matches and the
value falls to 0.
Read aabaabaab. pi[8] is 6: aabaab is both the first six characters and
the last six, and those two copies OVERLAP in the middle three. A border is
allowed to overlap itself.
## What most people try first
For each i, try every length from i downwards and compare. That is
O(n^2) character comparisons in the worst case. At n = 200000 one letter
repeated gives about 2 * 10^10 comparisons. The method below does about
4 * 10^5.
## Extending by one character
Suppose pi[i-1] = j, so s[0..j-1] is the longest border ending at i-1.
j = pi[i-1]
while j > 0 and s[i] != s[j]: j = pi[j-1]
if s[i] == s[j]: j = j + 1
pi[i] = j
If s[i] equals s[j] the border grows by one. If it does not, the next
candidate is the longest border OF THAT BORDER, which is pi[j-1], and the
loop follows that chain down.
## Why it is correct, and why it is linear
Any border ending at i has, after dropping its last character, a border
ending at i-1. So every candidate is on the chain j, pi[j-1],
pi[pi[j-1]-1], and nothing outside the chain can be missed.
The cost is linear because j rises by at most 1 per position, so it rises at
most n times in total, and every iteration of the inner loop strictly
DECREASES j. A quantity that goes up n times cannot come down more than
n times, so the inner loop runs at most n times over the whole run.
## The one line that breaks it
Setting pi[i] to 0 on a mismatch instead of following the chain. On
aabaaab the correct answer is 0 1 0 1 2 2 3 and that version prints
0 1 0 1 2 0 1, which was confirmed by running it. It is right on most inputs,
which is what makes it dangerous.
Constraints - `1 ≤ length of s ≤ 200000` - `s` contains only lowercase English letters
Input
A single line containing the string s, of lowercase English letters.
Output
Print the n values of the prefix function on one line, separated by single spaces, in index order from 0. There is no trailing space and no other text.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.