Loading [MathJax]/jax/output/CommonHTML/jax.js

差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン両方とも次のリビジョン
programming_algorithm:dynamic_programming:longest_common_subsequence [2018/05/23] ikatakosprogramming_algorithm:dynamic_programming:longest_common_subsequence [2019/01/09] ikatakos
行 117: 行 117:
     * Aにおいて、''bgn_idx''より右に文字 bk が存在する <=> 最長共通部分列"Tmax+bk"が存在し、暫定最長共通部分列長を|Tmax|+1に延長できる     * Aにおいて、''bgn_idx''より右に文字 bk が存在する <=> 最長共通部分列"Tmax+bk"が存在し、暫定最長共通部分列長を|Tmax|+1に延長できる
     * 延長できる場合、L に追加する     * 延長できる場合、L に追加する
 +
 +=====具体的な最長共通部分列=====
 +
 +  * [[wp>Longest_common_subsequence_problem]]
 +
 +|S|×|T| の配列上でDPを行い、途中の計算結果を保存しておくことで、最長共通部分列と共に、その具体例を構築することが出来る。
 +
 +S1...iT1...j のLCSの長さを Li,j とする。
 +
 +==Si+1=Tj+1 の時==
 +
 +LCS長は1文字拡張できる。Li+1,j+1=Li,j+1
 +
 +==それ以外の時==
 +
 +LCS長は、片方の末尾を1文字削った2通りの長い方となる。 Li+1,j+1=max(Li+1,j,Li,j+1)
 +
 +これで、i=1..|S|j=1..|T| の2重ループでDPテーブルを小さい方から埋めていくことで、DP[|S|][|T|] が最終的なLCS長となる。
 +
 +で、具体的な文字列は、DP[|S|][|T|] から逆向きに復元する。
 +
 +==DP[i][j]=DP[i][j1] または DP[i][j]=DP[i1][j] の時==
 +
 +同じである数字の方に移動する。両方同じ場合は、具体例が1つ構築できればいい場合は適当に1つ選んで移動する。
 +
 +==それ以外の時==
 +
 +Si=Tj であるはずなので、それをLCSに加え、(i1,j1) に移動する。
 +
 +<code>
 +      0 1 2 3 4 5 6 7
 +        M Z J A W X U
 +0   | 0 0 0 0 0 0 0 0
 +1 X |⓪ 0 0 0 0 0 1 1
 +2 M | 0❶① 1 1 1 1 1
 +3 J | 0 1 1❷ 2 2 2 2
 +4 Y | 0 1 1② 2 2 2 2
 +5 A | 0 1 1 2❸③③ 3
 +6 U | 0 1 1 2 3 3 3❹  丸付きの数字を辿っていき、
 +7 Z | 0 1 2 2 3 3 3④  黒丸の数字を拾っていくと、LCS(の1つ)は MJAU と復元できる
 +</code>
  
  
programming_algorithm/dynamic_programming/longest_common_subsequence.txt · 最終更新: by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0