AT_abc285_b [ABC285B] Longest Uncommon Prefix

题目描述

给定一个由小写英文字母组成、长度为 $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$ 时的答案，输出一个整数。

输入输出样例 #1

输入 #1

6
abcbac

输出 #1

5
1
2
0
1

说明/提示

限制条件

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

样例解释 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$。

由 ChatGPT 4.1 翻译