Longest Substring

For a string $S$ of length $n ≥ 1$ and a positive integer $k$ ($1 ≤ k ≤ n$), a non-empty substring of $S$ is called a $k$-substring if the substring appears exactly $k$ times. These $k$ occurrences may overlap. For example, if $S =$ "ababa", the $k$-substrings of $S$ for every $k = 1, \dots , 5$ are as follows.

• There are four $1$-substrings in $S$: "abab", "ababa", "bab", and "baba", because each appears exactly once. "aba" is not a $1$-substring because it appears twice.
• There are four $2$-substrings: "ab", "aba", "b", and "ba". "ab" appears exactly twice without overlapping. The two occurrences of "aba" overlap at the character "a", and it does not appear three times.
• There is only one $3$-substring, "a".
• There are no $4$-substrings or $5$-substrings.

For a $k$-substring $T$ of $S$, let $d(T)$ be the maximum number of disjoint occurrences of $T$ in $S$. For example, "ab" can be selected twice without overlapping, so $d("ab") = 2$. For the $2$-substring "aba", $d("aba") = 1$, because two of its occurrences cannot be chosen without overlapping. For the $3$-substring "a", $d("a") = 3$.

Let $f(k)$ be the length of the longest $k$-substring $T$ among those with the largest $d(T)$, for $1 ≤ k ≤ n$. For $S =$ "ababa", $f(1) = 5$, $f(2) = 2$, $f(3) = 1$, and $f(4) = f(5) = 0$.

The input is a single line containing the string $S$ of length $n$ ($1 ≤ n ≤ 50\,000$), consisting of lowercase English letters.

Print exactly one line with $n$ nonnegative integers separated by spaces: $f(1)$ $f(2)$ $\dots$ $f(n)$. If there is no $k$-substring for some $k$, then $f(k)$ is $0$.