题目描述

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

找出在 $S$ 中作为连续子字符串出现两次或更多的非空字符串的最大长度（不能重叠）。

更正式地说，找到最大的正整数 $len$，使存在整数 $l_1$ 和 $l_2$（$1 \leq l_1, l_2 \leq N - len + 1$），满足以下条件：

• $l_1 + len \leq l_2$
• 对于 $0 \leq i < len$，有 $S[l_1+i] = S[l_2+i]$

如果不存在这样的整数 $len$，则输出 $0$。

约束条件

• $30\%的数据2 \leq N \leq100$ $100\%的数据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 + len \leq l_2$ 的整数对 $l_1$ 和 $l_2$。

示例输入2

2
xy

示例输出2

0

没有符合条件的非空字符串。

示例输入3

13
strangeorange

示例输出3

5