不重叠子串

题目描述

给定一个长度为 $N$ 的字符串 $S$。

请回答：作为 $S$ 的连续子串不重叠地出现 $2$ 次以上的非空字符串中，最长的长度。

更严格地说：

• $l_1 + len \leq l_2$
• $S[l_1+i] = S[l_2+i]（i = 0, 1, ..., len - 1）$

求满足以上条件的整数 $l_1$, $l_2$（$1 \leq l_1, l_2 \leq N - len + 1$）存在的正整数 $len$ 的最大值。如果这样的 $len$ 不存在，则输出 $0$。

输入格式

输入按以下格式从标准输入给出：

$N$
$S$

输出格式

输出作为 $S$ 的连续子串不重叠地出现 $2$ 次以上的非空字符串中，最长的长度。如果这样的非空字符串不存在，则输出 $0$。

样例

5
ababa

2

满足条件的字符串有 a, b, ab, ba。这些长度中的最大值 $2$ 就是答案。 注意 aba 虽然作为 $S$ 的连续子串出现了 $2$ 次，但无法取到满足 $l_1 + len \leq l_2$ 的 $l_1$, $l_2$。

2
xy

0

不存在满足条件的非空字符串。

13
strangeorange

5

数据范围

• $2 \le N \le 5 \times 10^3$
• $|S| = N$
• $S$ 由小写英文字母组成