読者です 読者をやめる 読者になる 読者になる

最長共通部分列 Longest Common Subsequence

最長共通部分列とは

最長共通部分列(Common Longest Subsequence)とは、2つの与えられてた列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を求めたいとする。この時、以下の2つに場合分けして考える事ができる

  • ⅰ) 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の長さと置いた時、

ソースコード