分数: 500 点
问题陈述
给定的是一个字符串 S 长度 N.
求出出现两次或以上的非空字符串的最大长度 S 作为连续的子字符串,不重叠。
更正式地说,找到最大正整数 len 使得存在整数 l_1 和 l_2 ( 1 \leq l_1, l_2 \leq N - len + 1 )满足以下条件:
-
l_1 + len \leq l_2
-
S[l_1+i] = S[l_2+i] (i = 0, 1, ..., len - 1)
如果没有这样的整数 len,打印 0.
约束
- 2 \leq N \leq 5 \times 10^3
- |S| = N
- S 由小写英文字母组成。
输入
输入由标准输入按以下格式给出:
N S
输出
打印出现两次或多次的非空字符串的最大长度 S 作为连续的子字符串,不重叠。如果不存在这样的非空字符串,则打印 0 代替。
示例输入 1
5 ababa
示例输出 1
2
满足条件的字符串为: a, b, ab,和 ba。其中最大长度为 2,这就是答案。
请注意 aba 出现两次 S 作为连续子字符串,但没有整数对 l_1 和 l_2 在声明中提到, l_1 + len \leq l_2.
示例输入 2
2 xy
示例输出 2
0
没有非空字符串满足条件。
示例输入 3
13 strangeorange
示例输出 3
5