/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
英小文字からなる長さ N の文字列 S が与えられます。 S の x 文字目 (1 \le x \le N) は S_x です。
i=1,2,\dots,N-1 それぞれについて、以下の条件を全て満たす最大の非負整数 l を求めてください。
- l+i \le N である。
- 全ての 1 \le k \le l を満たす整数 k について、 S_{k} \neq S_{k+i} を満たす。
なお、 l=0 は常に条件を満たすことに注意してください。
制約
- N は 2 \le N \le 5000 を満たす整数
- S は英小文字からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
N-1 行にわたって出力せよ。そのうち x 行目 (1 \le x < N) には i=x とした場合の答えを整数として出力せよ。
入力例 1
6 abcbac
出力例 1
5 1 2 0 1
この入力では、 S= abcbac です。
- i=1 のとき、 S_1 \neq S_2, S_2 \neq S_3, \dots ,S_5 \neq S_6 であるため、 最大値は l=5 です。
- i=2 のとき、 S_1 \neq S_3 ですが S_2 = S_4 であるため、 最大値は l=1 です。
- i=3 のとき、 S_1 \neq S_4, S_2 \neq S_5 ですが S_3 = S_6 であるため、 最大値は l=2 です。
- i=4 のとき、 S_1 = S_5 であるため、 最大値は l=0 です。
- i=5 のとき、 S_1 \neq S_6 であるため、 最大値は l=1 です。
Score : 200 points
Problem Statement
You are given a string S of length N consisting of lowercase English letters. The x-th (1 \le x \le N) character of S is S_x.
For each i=1,2,\dots,N-1, find the maximum non-negative integer l that satisfies all of the following conditions:
- l+i \le N, and
- for all integers k such that 1 \le k \le l, it holds that S_{k} \neq S_{k+i}.
Note that l=0 always satisfies the conditions.
Constraints
- N is an integer such that 2 \le N \le 5000.
- S is a string of length N consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
N S
Output
Print (N-1) lines. The x-th (1 \le x < N) line should contain the answer as an integer when i=x.
Sample Input 1
6 abcbac
Sample Output 1
5 1 2 0 1
In this input, S= abcbac.
- When i=1, we have S_1 \neq S_2, S_2 \neq S_3, \dots, and S_5 \neq S_6, so the maximum value is l=5.
- When i=2, we have S_1 \neq S_3 but S_2 = S_4, so the maximum value is l=1.
- When i=3, we have S_1 \neq S_4 and S_2 \neq S_5 but S_3 = S_6, so the maximum value is l=2.
- When i=4, we have S_1 = S_5, so the maximum value is l=0.
- When i=5, we have S_1 \neq S_6, so the maximum value is l=1.