文字列の編集距離
編集距離とは，以下の三種類の操作によって，一つの文字列を別の文字列に変形するのに必要な最小回数です．
- 挿入 ：文字列に一つの文字列を挿入する．
- 削除 : 文字列から一つの文字を削除する．
- 置換 : 文字列の中の一文字を別な文字に置き換える．
例えば，文字列$s_1$=”abcd”を文字列$s_2$=”acef”に変形するためには，$s_1$のbを削除し，$s_1$のdをeへ置換，$s_1$の末尾に文字fを挿入すれば，編集距離３で$s_1$を$s_2$に変形することができます．
次に，動的計画法を用いて編集距離を求めます．
$dp[i][j] :=$ $S$の$i$文字目までの文字列を$T$ の$j$文字目までの文字列へ変換する編集距離
と定義します．すると，
dp[i][j] = min\{dp[i-1][j]+1,\; dp[i][j-1]+1,\;dp[i-1][j-1]+C\}\\
C=1 \quad (S_i \neq T_i )\\
C=0 \quad (S_i = T_i )
のように$dp[i][j]$を求めることが出来ます．文字列$S_1S_2...S_i$を文字列$T_1T_2...T_j$へ変換する操作の候補として以下の３つが挙げられます．上の数式と対応させると以下の通りです．
- $dp[i-1][j]+1 \to\;$文字列$S_1S_2 ...S_{i-1}$を文字列$T_1 T_2...T_j$に変換した後に$S_i$を削除する
- $dp[i][j-1]+1 \to\;$文字列$S_1S_2 ...S_{i}$を文字列$T_1 T_2...T_{j-1}$に変換した後に$T_j$を挿入する
- $dp[i-1][j-1]+C \to\;$文字列$S_1S_2 ...S_{i-1}$を文字列$T_1 T_2...T_{j-1}$に変換した後,$S_i=T_j$なら変換終了，$S_i \neq T_j$なら$S_i$を$T_j $に置換する．
AOJの問題，編集距離で今回の動的計画法を実装しました．
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void chmin(ll &a, const ll &b){
if (a>b) a = b;
}
int main() {
string s, t;
cin >> s >> t;
ll slen = s.size(), tlen = t.size();
ll INF = 101010;
vector<vector<ll>> dp(slen+1, vector<ll>(tlen+1, INF));
for(ll i=0; i<=slen; i++) dp[i][0] = i;
for(ll j=0; j<=tlen; j++) dp[0][j] = j;
for(ll i=1; i<=slen; i++){
for(ll j=1; j<=tlen; j++){
chmin(dp[i][j], dp[i-1][j]+1);
chmin(dp[i][j], dp[i][j-1]+1);
if(s[i-1] == t[j-1]) chmin(dp[i][j], dp[i-1][j-1]);
else chmin(dp[i][j], dp[i-1][j-1]+1);
}
}
cout << dp[slen][tlen] << endl;
return 0;
}