文字列の編集距離

編集距離とは，以下の三種類の操作によって，一つの文字列を別の文字列に変形するのに必要な最小回数です．

挿入：文字列に一つの文字列を挿入する．
削除 : 文字列から一つの文字を削除する．
置換 : 文字列の中の一文字を別な文字に置き換える．

例えば，文字列$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;
}

参考

DP（動的計画法）でレーベンシュタイン距離（編集距離）問題を解くまでの過程メモ

編集距離（レーベンシュタイン距離）の求め方

Tree Edit Distance (and Levenshtein Distance)