差分
この文書の現在のバージョンと選択したバージョンの差分を表示します。
| 両方とも前のリビジョン 前のリビジョン | |||
|
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つ選んで移動する。 |
| ==それ以外の時== | ==それ以外の時== | ||
