差分

この文書の現在のバージョンと選択したバージョンの差分を表示します。

この比較画面にリンクする

両方とも前のリビジョン 前のリビジョン
programming_algorithm:dynamic_programming:longest_common_subsequence [2019/01/09]
ikatakos
programming_algorithm:dynamic_programming:longest_common_subsequence [2019/01/09] (現在)
ikatakos
ライン 122: ライン 122:
   * [[wp>​Longest_common_subsequence_problem]]   * [[wp>​Longest_common_subsequence_problem]]
  
-$|S| \times |T|$ の配列上でDPを行い、途中の計算結果を保存しておくことで、最長共通部分列と共に、その具体例を構築することが出来る。+$(|S|+1) \times ​(|T|+1)$ の配列上でDPを行い、途中の計算結果を保存しておくことで、最長共通部分列と共に、その具体例を構築することが出来る。 
 + 
 +===DPテーブルの構築===
  
 $S_{1 ... i}$ と $T_{1 ... j}$ のLCSの長さを $L_{i,j}$ とする。 $S_{1 ... i}$ と $T_{1 ... j}$ のLCSの長さを $L_{i,j}$ とする。
 +
 +$L_{0,​j}=0,​L_{i,​0}=0$ とする。
  
 ==$S_{i+1}=T_{j+1}$ の時== ==$S_{i+1}=T_{j+1}$ の時==
ライン 134: ライン 138:
 LCS長は、片方の末尾を1文字削った2通りの長い方となる。 $L_{i+1,​j+1}=max(L_{i+1,​j},​L_{i,​j+1})$ LCS長は、片方の末尾を1文字削った2通りの長い方となる。 $L_{i+1,​j+1}=max(L_{i+1,​j},​L_{i,​j+1})$
  
-これで、$i=1 .. |S|$、$j=1 .. |T|$ の2重ループでDPテーブルを小さい方から埋めていくことで、$DP[|S|][|T|]$ が最終的なLCS長となる。+これで、$i=1 .. |S|$、$j=1 .. |T|$ の2重ループでDPテーブルを小さい方から埋めていくことで、$L_{|S|,|T|}$ が最終的なLCS長となる。 
 + 
 +===具体例の構築===
  
-で、具体的な文字列は、$DP[|S|][|T|]$ ​から逆向きに復元する。+具体的な文字列は、DPテーブルから逆向きに復元する。$(i,​j)=(|S|,​|T|)$ とする。
  
-==$DP[i][j]=DP[i][j-1]$ または $DP[i][j]=DP[i-1][j]$ の時==+==$L_{i,j}=L_{i,j-1}$ または $L_{i,j}=L_{i-1,j}$ の時==
  
-同じである数字の方に移動する。両方同じ場合は、具体例が1つ構築できればいい場合は適当に1つ選んで移動する。+同じである数字の方に$(i,j)$を移動する。両方同じ場合は、具体例が1つ構築できればいい場合は適当に1つ選んで移動する。
  
 ==それ以外の時== ==それ以外の時==
programming_algorithm/dynamic_programming/longest_common_subsequence.txt · 最終更新: 2019/01/09 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0