Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。
・問題 "Edit Distance (Levenshtein Distance)"
https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_E
・編集距離
僕が作成、提出したコードは、以下のとおりです。
Aizu Online Judge in C++ #DPL_1_E : Edit Distance (Levenshtein Distance)
/* Aizu Online Judge in C++ #DPL_1_E : Edit Distance (Levenshtein Distance) https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_E 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ string s1,s2; cin>>s1>>s2; int ss1=(int)s1.size(); int ss2=(int)s2.size(); vector<vector<int> > dp(ss1+1,vector<int>(ss2+1)); for(int i=0;i<=ss1;i++){ dp[i][0]=i; } for(int i=0;i<=ss2;i++){ dp[0][i]=i; } for(int i=1;i<=ss1;i++){ for(int j=1;j<=ss2;j++){ int Delete=dp[i-1][j]+1; int Insert=dp[i][j-1]+1; int Change=dp[i-1][j-1]+((s1[i-1]==s2[j-1]) ? 0 : 1); dp[i][j]=min({Delete,Insert,Change}); } } cout<<dp[ss1][ss2]<<endl; return 0; }
設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/