Who Says a Pun?

题目描述

给定长度为 $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$。

输入格式

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

输出格式

输出作为不重叠的连续子串在 $S$ 中出现两次或更多次的非空字符串的最大长度。如果不存在这样的非空字符串，则输出 $0$。

5
ababa

2

2
xy

0

13
strangeorange

5

提示

$2 \leq N \leq 5 \times 10^3$ $|S| = N$ $S$ 由小写英文字母组成。满足条件的字符串有：$a$、$b$、$ab$ 和 $ba$。它们的最大长度为 $2$，这就是答案。 注意 $aba$ 在 $S$ 中作为连续子串出现了两次，但不存在题目中提到的满足 $l_1 + len \leq l_2$ 的一对整数 $l_1$ 和 $l_2$。
没有满足条件的非空字符串。

标签: AtCoder|abc141E

来源

AtCoder|abc141E