分数: 200 点
问题陈述
给你一个字符串 S 长度 N 由小写英文字母组成。 的 x-th (1 \le x \le N) 的字符 S is S_x.
对于每个 i=1,2,\dots,N-1,找到最大非负整数 l 满足以下所有条件:
- l+i \le N,和
- 对于所有整数 k 这样 1 \le k \le l,它认为 S_{k} \neq S_{k+i}.
请注意 不包括 l=0 始终满足条件。
约束
- N 是一个整数,使得 2 \le N \le 5000.
- S 是一个长度为的字符串 N 由小写英文字母组成。
输入
输入由标准输入按以下格式给出:
N S
输出
打印 (N-1) 行。 的 x-th (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.