問題
長さ N の文字列 S が与えられます。
非空文字列であって、S の連続する部分文字列として重ならずに 2 回以上現れるもののうち、最長のものの長さを答えてください。
より厳密には、
- l_1 + len <= l_2
- S[l_1+i] = S[l_2+i] (i = 0, 1, …, len – 1)
を満たす整数 l_1 , l_2 ( 1 <= l_1, l_2 <= N – len + 1 ) が存在するような正整数 len の最大値を求めてください。そのような len が存在しないときは、0 を出力してください。
制約
- 2 ≤ N ≤ 5 * 10^3
- |S| = N
- S は英小文字から成る
考えたこと
要するに同じ部分文字列で最長のものを探せばよいです。
こういうのはだいたいSを二つ用意して重ねてずらしていけば良い(ような気がしている)ので今回もそれに習えば行けそうだったのでそうしました。
制約もn^2してね！という感じだし同じ文字を使わないようにだけ気をつけて実装すれば良いでしょう。
AC。素直な問題でした。
