最初の特性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/06/22 05:55 UTC 版)
二つの列の最後の要素は同じであるとする。これらの最長共通部分列を求めるには、それぞれの要素から最後の要素を取り除いた列の最長共通部分列を見つけ、そしてその最長共通部分列に取り除かれた要素を追加すればよい。 例として、ここに同じ最終要素を持つ二つの列(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の最長共通部分列問題に帰着されたことに注意せよ。
※この「最初の特性」の解説は、「最長共通部分列問題」の解説の一部です。
「最初の特性」を含む「最長共通部分列問題」の記事については、「最長共通部分列問題」の概要を参照ください。
ウィキペディア小見出し辞書の「最初の特性」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 最初の特性のページへのリンク
