题目描述

長さ $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

2
xy

0

13
strangeorange

5

提示

制約

• $2\ <\ =\ N\ <\ =\ 5\ \times\ 10^3$
• $|S|\ =\ N$
• $S$ は英小文字から成る

Sample Explanation 1

条件を満たす文字列として、a, b, ab, ba が考えられます。これらの長さの最大値 $2$ が答えです。 aba は $S$ の連続する部分文字列として $2$ 度現れますが、$l_1\ +\ len\ \leq\ l_2$ を満たすような $l_1$ , $l_2$ が取れないことに注意してください。

Sample Explanation 2

条件を満たす非空文字列は存在しません。