题目描述

英小文字からなる長さ $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$ $S$

输出格式

$N-1$ 行にわたって出力せよ。そのうち $x$ 行目 $(1\ \le\ x\ <\ N)$ には $i=x$ とした場合の答えを整数として出力せよ。

题目大意

给定 $N$，以及长度为 $N$ 只含英文小写字母的字符串 $S$，对于 $1 \le i \le N-1$，分别回答以下询问（记 $S_k$ 为 $S$ 的第 $k$ 个字符，从 $1$ 开始编号）：

找到最大的 $l$ ，使得对于所有 $1\le j \le l$，都满足 $j+l \le N$ 并且 $S_j$ 与 $S_{j+i}$ 不相同。如果不存在这样的 $l$，输出 $0$，否则输出 $l$。

6
abcbac

5
1
2
0
1

提示

制約

• $N$ は $2\ \le\ N\ \le\ 5000$ を満たす整数
• $S$ は英小文字からなる長さ $N$ の文字列

Sample Explanation 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$ です。