レーベンシュタイン距離
概要
列 $s$ のに対して以下の操作を行えるとする．
- 任意の文字を 1 つ削除
- 任意の場所に文字を 1 つ挿入
- 任意の文字を 1 つ選び，任意の文字に置き換える
$s$ から $t$ を構成するのに必要な操作回数の最小値を レーベンシュタイン距離 (Levenshtein Distance) といい，簡単な DP で求められる．
計算量
$O(mn)$ ($m, n$ は引数の長さ)
実装
template <class String>
int LevenshteinDistance(const String &s, const String &t) {
static int dp[2048][2048]; // 16 MB
int n = s.size(), m = t.size();
rep(i, n + 1) dp[i][0] = i;
rep(i, m + 1) dp[0][i] = i;
rep(i, n) rep(j, m) {
dp[i + 1][j + 1] = std::min(dp[i][j + 1], dp[i + 1][j]) + 1;
dp[i + 1][j + 1] = std::min(dp[i + 1][j + 1], dp[i][j] + (s[i] != t[j]));
}
return dp[n][m];
}
検証
yukicoder No. 225 http://yukicoder.me/no/225