Echoes
A text is read letter by letter. For each letter, find the length of the longest piece that ends at this letter and has occurred before, that is, ended at one of the previous letters. Pieces may overlap: in the string “aaaa” the fourth letter has an echo of length 3, because “aaa” ended at the third. If this letter has not occurred in the text before, the echo is 0.
The third test is Eugene Onegin (the Russian original) brought to one form (lowercase letters, е instead of ё, a space instead of a line break); its longest echo is « и в молчаливом кабинете» (“ and in the silent study”), 24 characters including the space. The fourth is the genome of phage λ, 48,502 nucleotides.
Input
One line: a text from 1 to 3 · 10⁵ characters long in UTF-8, with no spaces at the start or end. Length is counted in characters, not bytes.
Output
On one line, separated by spaces, the echo of each letter in order.
Examples
Example 1
abcbc
0 0 0 1 2
Example 2
колокол
0 0 0 1 1 2 3
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
If letter i has an echo of length L, what can the echo of letter i + 1 be? Not more than L + 1: a piece that ends at i + 1 and occurred before has also occurred before without its last letter.
2Hint 2
The longest suffix of what has been read that also ended earlier is exactly what the suffix link in the automaton points to. The automaton is built letter by letter, so the answer can be read off after each step.
3The idea
Build the suffix automaton online. After letter i the state last is the class of the string of the first i letters, and its ends are the single position i. The suffix link leads to the class of the longest suffix with more ends, that is, one that also ended earlier. Its length len(link(last)) is the answer.
4Walkthrough
This is the ordinary construction from the article, except that after each letter we write out the len of the new state’s link. A copy changes nothing in the answer for letters already read, and it is exactly what the new link needs: if a suffix occurred before but its class is wider, the link points to a copy of the right length.
4+Solution
5Complexity
O(n) for the whole text: construction is linear, and the answer at each step is a single read of a length.
6Common mistakes
- Looking back with find. This is
wrong.py: the echo grows by at most one, so we try lengths from the previous answer plus one downwards and search for the piece in what has been read. The answers are correct, but a failed search reads everything read so far. Already on Onegin in the third test the echo is five characters on average, almost every letter ends in a failure, and that is 139 thousand passes over the text. - No copies. If q is made the new state’s link even when len(q) is greater than len(p) + 1, the length behind the link exceeds the real echo. This shows already in the first example, at the fourth letter, and in the ninth test of random a and b a copy appears at almost every step. On the other hand, the Fibonacci word of the eighth test has not a single copy.
- An echo without overlap. In the string of nothing but “a” in the seventh test the answer for the i-th letter is i − 1: the previous occurrence may overlap the current one.
- Output. There are 3 · 10⁵ answers, and printing them one at a time is slow; build the whole line.