最长非公共前缀

题目描述

给定一个长度为 $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 \lt N$) 输出当 $i=x$ 时答案的整数。

样例

6
abcbac

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$。

数据范围

• $N$ 是满足 $2 \le N \le 5000$ 的整数。
• $S$ 是由小写英文字母组成的长度为 $N$ 的字符串。