最長共通部分列 Longest Common Subsequence
最長共通部分列とは
最長共通部分列(Common Longest Subsequence)とは、２つの与えられてた列X = {x1, x2, …, xm}とY = {y1, y2, …, yn}の最長の共通部分列のことである。 例えばX = {a, b, c, d, f}, Y = {a, f, b, d, a}の最長共通部分列は{a, b, d}となる。注意として、部分列は要素が連続していなくて良い。
最長共通部分列の見つけ方
これは動的計画法によって解くことができる。 Xm = {x1, x2, … , xm}, Yn = {y1, y2, … , yn}とする。XmとYnのLCSを求めたいとする。この時、以下の２つに場合分けして考える事ができる
- ⅰ) xm == ynの時
- ⅱ) xm != ynの時
ⅰ) xm == ynの時
Xm-1とYn-1のLCSにxm(=yn)を連結したものがXmとYnのLCSとなる。
ⅱ) xm != ynの時
「Xm-1とYnのLCS」と「XmとYn-1のLCS」を比べ長い方がXmとYnのLCSとなる。
ⅰ)ⅱ)より漸化式は以下のようになる。
dp[m][n]をXmとYnのLCSの長さと置いた時、
