最長共通部分列問題
二つの列の最後の要素は同じであるとする。これらの最長共通部分列を求めるには、それぞれの要素から最後の要素を取り除いた列の最長共通部分列を見つけ、そしてその最長共通部分列に取り除かれた要素を追加すればよい。
例として、ここに同じ最終要素を持つ二つの列(BANANA)と(ATANA)がある。
共通する最終要素を取り除くことを、共通ではない最終要素が見つかるまで、繰り返す。取り除かれた列は(ANA)である。
考察すべき列は(BAN)と(AT)であり、最後の二つの配列の最長共通部分列は(A)であることが容易にわかる。
取り出した要素(ANA)を追加し(AANA)となる。これが元の配列の最長共通部分列であることは容易に確かめられる。
接頭辞に関して、
if xn=ym, then LCS(Xn, Ym) = (LCS( Xn-1, Ym-1), xn)
が成り立つ。ここで最後の括弧は、列の最後にxnを追加することを表す。 XnとYmの最長共通部分列問題が、より短い列 Xn-1と Ym-1の最長共通部分列問題に帰着されたことに注意せよ。
最長共通部分列のテーブルにおいて、最長共通部分列の行の計算に唯一要求されるのは、現在の行と次の行である。なお、長い配列の場合、それらの配列はおびただしく長くなるので、たくさんの記憶領域が要求される。記憶領域を節約するには、実際の部分列を保存しない事である。しかし、部分列の長さと方向矢印は保存する必要がある。それは、以下のテーブルのようにである。
実際の部分列は、”トレースバック”手順で推測する。それは続く逆向き矢印であり、テーブルの最後のセルから開始する。トレースバックでは長さは減少する。配列に必須なのは共通の要素である。いくつかの経路が可能であり、その場合、セルに二つの矢印がある。以下は、その解析のためのテーブルである。セルの色の付いた数字は減少についての長さである。太字の数字はトレースした配列 (GA) である。