Given a non-empty string S whose length N does not exceed \(10^6\). We will assume that the elements of the string are numbered from 1 to N.
For each position of the i character in the string, we will be interested in the substring that ends at that position and matches some beginning of the whole string. Generally speaking, there will be several such substrings, at least two. The longest of them has the length i, we will not be interested in it. And we will be interested in the longest of the remaining such substrings (note that such a substring always exists — in the extreme case, if nothing else is found, an empty substring will do).
The value of the prefix function \(\pi[i]\) will be the length of this substring.
The prefix function is used in various string processing algorithms. In particular, it can be used to quickly solve the problem of finding the occurrence of one string in another ("search for a pattern in the text").
Required for all i from 1 to N to compute \(\pi[i] \).
Input
One string of length N, \(0 < N <= 10^6\), consisting of small Latin letters.
Output
Output
N numbers — prefix function values for each position, separated by spaces.
Examples
| # |
Input |
Output |
| 1 |
abracadabra |
0 0 0 1 0 1 0 1 2 3 4 |