[ABC141E] Who Says a Pun?
题意翻译
给你一个字符串,请找到两个**互相不重叠**且**完全相同**的子串,并输出它的最大长度。
题目描述
[problemUrl]: https://atcoder.jp/contests/abc141/tasks/abc141_e
長さ $ 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 $ を出力せよ。
输入输出样例
输入样例 #1
5
ababa
输出样例 #1
2
输入样例 #2
2
xy
输出样例 #2
0
输入样例 #3
13
strangeorange
输出样例 #3
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
条件を満たす非空文字列は存在しません。