当前没有测试数据。

B - 最长非公共前缀

分值 : $200$ 分

题目描述

给定一个长度为 $N$ 的字符串 $S$，其中每个字符 $S_x$ ($1 \le x \le N$) 都是小写英文字母。

对于每个 $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 \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$。