가장 긴 부분 문자열

길이가 $n ≥ 1$인 문자열 $S$와 양의 정수 $k$ ($1 ≤ k ≤ n$)에 대해, $S$의 비어 있지 않은 부분 문자열 $T$가 정확히 $k$번 나타나면 $T$를 $k$-부분 문자열이라고 한다. 이 $k$번의 출현은 서로 겹칠 수 있다. 예를 들어 $S =$ "ababa"이면 $k = 1, \dots , 5$에 대한 $k$-부분 문자열은 다음과 같다.

• $S$에서 정확히 한 번 나타나는 1-부분 문자열은 네 개이다. "abab", "ababa", "bab", "baba"가 그것이다. "aba"는 두 번 나타나므로 1-부분 문자열이 아니다.
• 2-부분 문자열은 네 개이다. "ab", "aba", "b", "ba"가 그것이다. "ab"는 겹치지 않게 정확히 두 번 나타난다. "aba"의 두 출현은 문자 "a"에서 겹치며, 세 번 나타나지는 않는다.
• 3-부분 문자열은 "a" 하나뿐이다.
• 4-부분 문자열과 5-부분 문자열은 존재하지 않는다.

$k$-부분 문자열 $T$에 대해 $d(T)$는 $S$에서 $T$의 출현 중 서로 겹치지 않는 출현을 최대 몇 개 고를 수 있는지를 뜻한다. 예를 들어 "ab"는 겹치지 않게 두 번 고를 수 있으므로 $d("ab") = 2$이다. 2-부분 문자열 "aba"는 겹치지 않게 두 번 고를 수 없으므로 $d("aba") = 1$이다. 3-부분 문자열 "a"는 $d("a") = 3$이다.

$f(k)$는 $1 ≤ k ≤ n$에 대해, $k$-부분 문자열 중 $d(T)$가 가장 큰 것들 가운데 가장 긴 $T$의 길이이다. $S =$ "ababa"이면 $f(1) = 5$, $f(2) = 2$, $f(3) = 1$, $f(4) = f(5) = 0$이다.

첫 줄에 길이 $n$ ($1 ≤ n ≤ 50\,000$)의 영어 소문자로 이루어진 문자열 $S$가 주어진다.

공백으로 구분한 $n$개의 음이 아닌 정수를 한 줄에 출력한다. 순서는 $f(1)$ $f(2)$ $\dots$ $f(n)$이다. 어떤 $k$에 대해 $k$-부분 문자열이 없으면 $f(k)$는 0이다.