ホーム > libalgo

レーベンシュタイン距離

概要

列 $s$ のに対して以下の操作を行えるとする.

  • 任意の文字を 1 つ削除
  • 任意の場所に文字を 1 つ挿入
  • 任意の文字を 1 つ選び,任意の文字に置き換える

$s$ から $t$ を構成するのに必要な操作回数の最小値を レーベンシュタイン距離 (Levenshtein Distance) といい,簡単な DP で求められる.

計算量

$O(|s||t|)$

実装

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

参考文系

レーベンシュタイン距離 - Wikipedia