【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; }
しっかり理解しきれていないのでまた整理する.
- 参考