回答編集履歴
1
説明に誤りがあったので訂正します（この問題で求めているのは編集距離じゃない）
test
CHANGED
|
@@ -1,5 +1,7 @@
|
|
|
1
|
-
これは
|
|
1
|
+
これは共通部分文字列の最大長を求めた後、その文字列を復元するっていう二つのステップからなってます。
|
|
2
2
|
|
|
3
|
-
|
|
3
|
+
最大長を求めるステップでは、`DP[i][j]`に「文字列Sの0〜i-1文字目までと、文字列Tの0〜j-1文字目までを使ったときの共通部分文字列の最大長」が入るようにDP表を更新してます。
|
|
4
4
|
|
|
5
|
+
|
|
6
|
+
|
|
5
|
-
「編集距離」で検索すると分かりやすい解説が出てくると思うので、調べてみてください。
|
|
7
|
+
類似の典型アルゴリズムに「編集距離」というのがありまして、これで検索すると分かりやすい解説が出てくると思うので、調べてみてください。
|