E - 谁说了一个双关语？

分数：500

问题描述

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

找出 $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$

输出

输出最大长度的至少出现两次的连续子字符串。如果不存在这样的非空字符串，输出 $0$。

5
ababa

2

满足条件的字符串有：a、b、ab 和 ba。它们中的最大长度为 $2$，即为答案。 请注意，aba 作为连续子字符串出现了两次，但是没有满足 $l_1 + len \leq l_2$ 的整数对 $l_1$ 和 $l_2$。

2
xy

0

没有满足条件的非空字符串。

13
strangeorange

5