\(\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 などを用います。