Longest Substring

문제

For a string $SS$ of length n ≥ 1 and a positive integer $kk$ (1 ≤ k ≤ n), a non-empty substring of $SS$ is called a $kk$-substring if the substring appears exactly $kk$ times. Such $kk$ occurrences are not necessarily disjoint, i.e., are possibly overlapping. For example, if $S=S\; =$ "ababa", the $kk$-substrings of $SS$ for every $k=1,\dots ,5k\; =\; 1,\; \backslash dots\; ,\; 5$ are as follows:

• There are four $11$-substrings in $SS$, "abab", "ababa", "bab", and "baba" because these substrings appear exactly once in $SS$. Note that "aba" is not a $11$-substring because it appears twice.
• There are four $22$-substrings in $SS$, "ab", "aba", "b", and "ba". The substring "ab" appears exactly twice without overlapping. Two occurrences of the substring "aba" are overlapped at a common character "a", but it does not appear three times or more.
• There is only one $33$-substring in $SS$, "a".
• Neither $44$-substrings nor $55$-substrings exist in $SS$.

For a $kk$-substring $TT$ of $SS$, let $d(T)d(T)$ be the maximum number of the disjoint occurrences of $TT$ in $SS$. For example, a $22$-substring $T=T\; =$ "ab" can be selected twice without overlapping, that is, the maximum number of the disjoint occurrences is two, so $d(T)=2d(T)\; =\; 2$. For a $22$-substring $T=T\; =$ "aba", it cannot be selected twice without overlapping, so $d(T)=1d(T)\; =\; 1$. For a $33$-substring $T=T\; =$ "a", it can be selected three times without overlapping, which is the maximum, so $d(T)=3d(T)\; =\; 3$.

Let $f(k)f(k)$ be the length of the longest one among all $kk$-substring $TT$ with the largest $d(T)d(T)$ for 1 ≤ k ≤ n. For example, $f(k)f(k)$ for $S=S\; =$ "ababa" and $k=1,\dots ,5k\; =\; 1,\; \backslash dots\; ,\; 5$ is as follows:

• For $k=1k\; =\; 1$, all $11$-substrings $TT$ can be selected only once without overlapping, so $d(T)=1d(T)\; =\; 1$. Thus, the longest one among all $11$-substrings with $d(T)=1d(T)\; =\; 1$ is "ababa", so $f(1)=5f(1)\; =\; 5$.
• For $k=2k\; =\; 2$, $d(T)=1d(T)\; =\; 1$ for $T=T\; =$ "aba", but $d(T)=2d(T)\; =\; 2$ for the other $22$-substrings $T=T\; =$ "ab", "b", "ba". Among $22$-substrings with $d(T)=2d(T)\; =\; 2$, "ab" and "ba" are the longest ones, so $f(2)=2f(2)\; =\; 2$.
• For $k=3k\; =\; 3$, $f(3)=1f(3)\; =\; 1$ because there is only one $33$-substring "a".
• For $k=4,5k\; =\; 4,\; 5$, there are no $kk$-substrings, so $f(4)=0f(4)\; =\; 0$ and $f(5)=0f(5)\; =\; 0$.

Given a string $SS$ of length $nn$, write a program to output $nn$ values of $f(k)f(k)$ from $k=1k\; =\; 1$ to $k=nk\; =\; n$. For the above example, the output should be $55$ $22$ $11$ $00$ $00$.

입력

Your program is to read from standard input. The input starts with a line containing the string $SS$ consisting of $nn$ (1 ≤ n ≤ 50\,000) lowercase alphabets.

출력

Your program is to write to standard output. Print exactly one line. The line should contain exactly $nn$ nonnegative integers, separated by a space, that represent $f(k)f(k)$ from $k=1k\; =\; 1$ to $k=nk\; =\; n$ in order, that is, $f(1)f(1)$ $f(2)f(2)$ $\dots \backslash dots$ $f(n)f(n)$. Note that $f(k)f(k)$ should be zero if there is no $kk$-substring for some $kk$.

ababa

5 2 1 0 0

aaaaaaaa

8 7 6 5 4 3 2 1