P14729 [ICPC 2022 Seoul R] Longest Substring

For a string $S$ of length $n \geq 1$ and a positive integer $k$ ($1 \leq k \leq n$), a non-empty substring of $S$ is called a $k$-substring if the substring appears **exactly** $k$ times. Such $k$ occurrences are not necessarily disjoint, i.e., are possibly overlapping. For example, if $S = \text{ababa}$, the $k$-substrings of $S$ for every $k = 1, ..., 5$ are as follows: - There are four 1-substrings in $S$, $\text{abab}$, $\text{ababa}$, $\text{bab}$, and $\text{baba}$ because these substrings appear exactly once in $S$. Note that $\text{aba}$ is not a 1-substring because it appears twice. - There are four 2-substrings in $S$, $\text{ab}$, $\text{aba}$, $\text{b}$, and $\text{ba}$. The substring $\text{ab}$ appears exactly twice without overlapping. Two occurrences of the substring $\text{aba}$ are overlapped at a common character $\text{a}$, but it does not appear three times or more. - There is only one 3-substring in $S$, $\text{a}$. - Neither 4-substrings nor 5-substrings exist in $S$. For a $k$-substring $T$ of $S$, let $d(T)$ be the maximum number of the disjoint occurrences of $T$ in $S$. For example, a 2-substring $T = \text{ab}$ can be selected twice without overlapping, that is, the maximum number of the disjoint occurrences is two, so $d(T) = 2$. For a 2-substring $T = \text{aba}$, it cannot be selected twice without overlapping, so $d(T) = 1$. For a 3-substring $T = \text{a}$, it can be selected three times without overlapping, which is the maximum, so $d(T) = 3$. Let $f(k)$ be the length of the longest one among all $k$-substring $T$ with the largest $d(T)$ for $1 \leq k \leq n$. For example, $f(k)$ for $S = \text{ababa}$ and $k = 1, ..., 5$ is as follows: - For $k = 1$, all 1-substrings $T$ can be selected only once without overlapping, so $d(T) = 1$. Thus, the longest one among all 1-substrings with $d(T) = 1$ is $\text{ababa}$, so $f(1) = 5$. - For $k = 2$, $d(T) = 1$ for $T = \text{aba}$, but $d(T) = 2$ for the other 2-substrings $T = \text{ab}$, $\text{b}$, $\text{ba}$. Among 2-substrings with $d(T) = 2$, $\text{ab}$ and $\text{ba}$ are the longest ones, so $f(2) = 2$. - For $k = 3$, $f(3) = 1$ because there is only one 3-substring $\text{a}$. - For $k = 4, 5$, there are no $k$-substrings, so $f(4) = 0$ and $f(5) = 0$. Given a string $S$ of length $n$, write a program to output $n$ values of $f(k)$ from $k = 1$ to $k = n$. For the above example, the output should be $5\ 2\ 1\ 0\ 0$.

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

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