最長共通部分列問題
入力配列の個数が任意の場合、動的計画法の解法は下記の計算量で解を与える。
O ( N ∏ i = 1 N n i ) . {\displaystyle O\left(N\prod _{i=1}^{N}n_{i}\right).}
より計算量の小さい方法が存在するが、それはしばしば、最長共通部分列の配列長か、アルファベット(=対象とする列に現れる要素)のサイズ、もしくはその両方に依存する。
注意:最長共通部分列は、必ずしも一意ではない。例として ”ABC” と ”ACB” の最長共通部分列は ”AB” と ”AC” の両方である。実際、最長共通部分列の定義が「長さ最大の共通部分列をすべて見つけること」であることも多い。このように問題を変更すると、計算量は増大してしまう。なぜならば、長さ最大の部分列の数は最悪の場合、指数関数的に増大する。入力配列が2つの場合でさえ同様である。
二つの配列を以下のように定義する:
X = (x1, x2...xm) ... X の接頭辞は、 X1, 2,...m Y = (y1, y2...yn) ... Y の接頭辞は、 Y1, 2,...n
LCS(Xi, Yj) は、Xi と Yj の接頭辞の最長共通部分列セットを代表する。 この配列セットは、以下を与える。
L C S ( X i , Y j ) = { ∅ if i = 0 or j = 0 L C S ( X i − 1 , Y j − 1 ) ⌢ x i if x i = y j longest ( L C S ( X i , Y j − 1 ) , L C S ( X i − 1 , Y j ) ) if x i ≠ y j {\displaystyle LCS\left(X_{i},Y_{j}\right)={\begin{cases}\emptyset &{\mbox{ if }}\ i=0{\mbox{ or }}j=0\\{\textrm {}}LCS\left(X_{i-1},Y_{j-1}\right)\frown x_{i}&{\mbox{ if }}x_{i}=y_{j}\\{\mbox{longest}}\left(LCS\left(X_{i},Y_{j-1}\right),LCS\left(X_{i-1},Y_{j}\right)\right)&{\mbox{ if }}x_{i}\neq y_{j}\\\end{cases}}}
LCS(R3, C1) は C と A を比較し、不一致。LCS(R3, C1) は二つの配列の最長(A)を得る。
LCS(R3, C2)は C と G を比較し、不一致。LCS(R3, C1) と LCS(R2, C2) は、共通の一つの要素を持っている。結果、LCS(R3, C2) は二つの配列 (A) と (G) となる。
LCS(R3, C3) は C と C を比較し、一致。C は LCS(R2, C2) に追加され、それは二つの配列 (A) と (G)、そして、(AC)と (GC) を得る。
LCS(R3, C4) は C と A を比較し、不一致。LCS(R3, C3) を結合させ、それは (AC) と (GC)、そしてLCS(R2, C4)は (GA) を含んでおり、全部で (AC)、(GC)、(GA) の三つの配列を与える。
最後にLCS(R3, C5)は C と T を比較し、不一致。結果は、LCS(R3, C5)の通り、(AC)、(GC)、そして (GA) の三つの配列を含む。
結果として、最後のセルは (AGCAT) と (GAC) に共通なすべての最長部分列を含んでいる。それらは (AC) と (GC) そして (GA) である。またこのテーブルは、最長共通部分列の接頭辞すべての可能な組み合わせを見ることができる。例えば (AGC) と (GA) の最長共通部分列は (A) と (G) である。