English version is in beta. All contents of the site should be already translated (mostly using machine translation), and everything should work properly. However, if you find any problems, please contact me.
The problem statement has been automatically translated from Russian. If the statement is not clear, or you have any comments about it, please contact me. Anyway, I hope that someday I will fix the translation manually.

Prefix function

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 a substring ending at this position and coinciding with some beginning of the entire string. Generally speaking, there will be several such substrings, at least two. The longest of them has length i, it will not interest us. And we will be interested in the longest of the other such substrings (note that such a substring always exists — in extreme cases, if nothing else is found, an empty substring will do).

The value of the prefix function π[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 line in another ("search for a sample in the text").

Required for all i from 1 to N calculate π[i].

Input data

One string of length N, 0 < N ≤ 10 6, consisting of small Latin letters.

Output data

Print N numbers — prefix function values for each position, separated by a space.

Examples
Input data
abracadabra
Output data
0 0 0 1 0 1 0 1 2 3 4

This problem on informatics

algoprog.ru © Petr Kalinin, GNU AGPL, github.com/petr-kalinin/algoprog | About the license for the site materials | Blog (in Russian)