Educational DP Contest / DP まとめコンテストが開始されました。
Educational DP Contest / DP まとめコンテストは終了しました。
\(\Theta(|S|\cdot |T|)\) 時間の DP が有名ですが、\(O(|S|+|T|+\delta(S, T)^2)\) 時間のアルゴリズムが存在します。ここで、\(S\) と \(T\) の LCS を \(L\) として、\(\delta(S, T) = (|S|-|L|) + (|T|-|L|)\) です。直感的には、\(S\) と \(T\) が似ているときほど高速です。
SA-IS + LCP 配列の線形構築 + 線形 RMQ などを用います。
投稿日時: 最終更新: