A7585. [ABC141E] Who Says a Pun?
编程题
普及+/提高
知识点
题目描述
给定一个长度为 $N$ 的字符串 $S$。
请你求出所有作为 $S$ 的连续子串且在 $S$ 中不重叠地出现至少两次的非空字符串中，最长的长度是多少。
更严格地说，求满足以下条件的正整数 $len$ 的最大值：
- $l_1 + len \leq l_2$
- $S[l_1 + i] = S[l_2 + i]\ (i = 0, 1, \ldots, len - 1)$
存在整数 $l_1, l_2$（$1 \leq l_1, l_2 \leq N - len + 1$）使上述条件成立。若不存在这样的 $len$，请输出 $0$。
请你求出所有作为 $S$ 的连续子串且在 $S$ 中不重叠地出现至少两次的非空字符串中，最长的长度是多少。
更严格地说，求满足以下条件的正整数 $len$ 的最大值：
- $l_1 + len \leq l_2$
- $S[l_1 + i] = S[l_2 + i]\ (i = 0, 1, \ldots, len - 1)$
存在整数 $l_1, l_2$（$1 \leq l_1, l_2 \leq N - len + 1$）使上述条件成立。若不存在这样的 $len$，请输出 $0$。
输入格式
输入以以下格式从标准输入读入。
> $N$ $S$
> $N$ $S$
输出格式
输出作为 $S$ 的连续子串且在 $S$ 中不重叠地出现至少两次的非空字符串中，最长的长度。如果不存在这样的非空字符串，则输出 $0$。
输入输出样例
输入 #1
5 ababa
输出 #1
2
输入 #2
2 xy
输出 #2
0
输入 #3
13 strangeorange
输出 #3
5
说明/提示
### 限制条件
- $2 \leq N \leq 5 \times 10^3$
- $|S| = N$
- $S$ 由小写英文字母组成
### 样例解释 1
满足条件的字符串有
### 样例解释 2
不存在满足条件的非空字符串。
- $2 \leq N \leq 5 \times 10^3$
- $|S| = N$
- $S$ 由小写英文字母组成
### 样例解释 1
满足条件的字符串有
a、b、ab、ba。这些字符串的最大长度为 $2$，因此答案为 $2$。注意，虽然 aba 作为 $S$ 的连续子串出现了两次，但无法取到满足 $l_1 + len \leq l_2$ 的 $l_1$ 和 $l_2$。### 样例解释 2
不存在满足条件的非空字符串。