【AOJ DPL1_E】Edit Distance (Levenshtein Distance)

• 問題

Edit Distance (Levenshtein Distance) | Aizu Online Judge

• 概要
  与えられた2つの文字列の編集距離を求める問題.

• 実装方針
  動的計画法を用いることで解を求めることができる. 2つの文字列のそれぞれi番目, j番目の編集距離ED(i, j)をもとめるには, min{ ED(i-1, j), ED(i, j-1), ED(i-1, j-1) + cost }とすれば良い. ただし, s1[i]==s2[j]の場合cost = 0となる. s1[i] != s2[j]ではcost = 1である.

• コード

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int dp[1001][1001];

#define rep(i,n) for(int i = 0 ; i < (int)n ; i++)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)

int main(){
  string s1, s2;

  cin >> s1;
  cin >> s2;

  rep(i, s1.length()+1) dp[i][0] = i;
  rep(j, s2.length()+1) dp[0][j] = j;
  
  REP(i, 1,  s1.length()+1){
    REP(j, 1, s2.length()+1){
      int cost = s1[i-1] == s2[j-1]?0:1;
      dp[i][j] = min(min(dp[i-1][j]+1, dp[i][j-1]+1), dp[i-1][j-1]+cost);
    }
  }
  
  cout << dp[s1.length()][s2.length()] << endl;
}

しっかり理解しきれていないのでまた整理する.

• 参考

d.hatena.ne.jp

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