1812. The Longest Prefix That Shows Up Again
Print the length of the longest prefix of s that also occurs starting at some
position other than 0. Print 0 if no prefix does.
The second copy MAY OVERLAP the first, and a length is wanted rather than a position.
abcabcd -> 3 abc occurs again at position 3
aaaa -> 3 aaa occurs again at position 1, overlapping
aabaabaab -> 6 aabaab occurs again at position 3, overlapping
abcdef -> 0
baaa -> 0 the first letter never returns
aaaa is the case to think about. The prefix aaa covers positions 0 to 2, and
it occurs again covering positions 1 to 3. Those share two characters and the
question still counts it. Demanding disjoint copies would answer 2 here and 3 on
aabaabaab; both were confirmed by running that version.
## What most people try first
For each start i > 0, walk forward while the characters agree with the prefix,
and keep the best. That is O(n^2): at n = 200000 identical characters it is
about 2 * 10^10 comparisons. The method below costs about 4 * 10^5.
## The largest value in the table
answer = max(pi[1], pi[2], ..., pi[n-1])
## Why the maximum is exactly the answer
pi[i] is the length of the longest prefix of s that ends at position i and
is not the whole of s[0..i]. Not being the whole of it means it starts at
i - pi[i] + 1, which is at least 1. So every value pi[i] with i >= 1 is a
prefix occurring at a position other than 0, and the largest of them is
achievable.
Conversely, if the prefix of length L occurs starting at some j >= 1, it ends
at i = j + L - 1, and pi[i] is the LONGEST prefix ending there, so
pi[i] >= L. So no length is missed.
pi[0] is excluded because it is always 0 and carries no information; including
it changes nothing but it is worth knowing why it is there.
## The boundary
n = 1. There is no position other than 0, so the answer is 0, and a program
that takes the maximum over an empty range must start that maximum at 0 rather
than at pi[0] of a one-element array.
## Cost
O(n) time and O(n) memory.
Constraints - `1 ≤ length of s ≤ 200000` - `s` contains only lowercase English letters - the two occurrences may overlap
Input
A single line containing the string s, of lowercase English letters.
Output
Print one integer on its own line: the length of the longest prefix of s that also begins at some position other than 0, counting a second copy that overlaps the first. Print 0 if there is none.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.