who says a pun? - abc 141 e
解法 1
dp[i][j] : 文字列 s の i 番目から始まる文字列と j 番目から始まる文字列の最大一致長さ
後ろから求めていく.
if (s[i] == s[j]) dp[i][j] = dp[i + 1][j + 1] + 1;
https://atcoder.jp/contests/abc141/submissions/14934072
解法 2
長さを二分探索し, 2 つの文字列の開始位置を全探索する.
一致判定はローリングハッシュ (ロリハ).
https://atcoder.jp/contests/abc141/submissions/14936863, O(N^2 logN), 1848 ms
解法 3
解法 2 の高速化.
長さ k 固定で, i 番目始まりの文字列のハッシュ値を得る.
長さ k は二分探索, 始まりの i 番目を探索で O(N logN).
同じハッシュ値があるかを map で調べる.
https://atcoder.jp/contests/abc141/submissions/14937753, O(N (logN)^2), 42 ms
解法4
解法 3 で, ローリングハッシュの代わりに set ですでに見た文字列を管理する.
長さ mid を二分探索. O(logN)
開始位置 i を探索. O(N)
ロリハじゃないので , 長さ mid, i はじめの文字列 t を毎回得る. O(N)
と同時に, すでに見た文字列に t があるか調べる.
https://atcoder.jp/contests/abc141/submissions/14938145, O(N^2 logN), 184 ms
解法 2 と違い, 長さが小さくなるほど s.substr の計算量が小さくなり, N^2 より NlogN に近くなる.
logN というのは, lower_bound.
