$$ \def\bra#1{\mathinner{\left\langle{#1}\right|}} \def\ket#1{\mathinner{\left|{#1}\right\rangle}} \def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}} $$

◇◇tech010:最長共通部分文字列◇◇

☆概要

2つの文字列$S,T$について、それぞれの文字列の共通部分文字列のなかで最も長いものを求める。

☆本文

DPテーブルを

DP[$i$][$j$]=S[$i$]とT[$j$]のペアは、共通部分列の何文字目か？

ととれば、素直に更新するだけで解ける。たとえば$S$="abcde", $T$="bcd"であるとき、S[0]!=T[0]なのでDP[0][0]=0だが、S[1]==T[0]であるのでDP[1][0]=1となる。ここで、DP[2][1]=DP[1][0]+1=2となり、この要領でDPテーブルを更新すれば最後に最大値を探すだけで最長共通部分文字列の長さがわかる。復元は容易。

☆問題

これはひとつの文字列のなかで2回以上登場する文字列の最長を求める問題だが、この考え方の応用で解ける。なお、Z-Algorithmを$N$回やることでも解ける。

戻る