2019-09-21 11:22:54 C++

C++

Copy Copied! Full
#include <bits/stdc++.h> using namespace std; vector<vector<int>> dp(1005,vector<int>(1005,100000000)); vector<vector<int>> pre(1005,vector<int>(1005,-1)); int main(void){ cin.tie(0); ios::sync_with_stdio(false); int d; string s1,s2; cin >> s1 >> s2; for(int i=0;i<=s1.size();i++)dp[i][0]=i,pre[i][0]=2; for(int i=0;i<=s2.size();i++)dp[0][i]=i,pre[0][i]=1; pre[0][0] = -1; for(int i=1;i<=s1.size();i++){ for(int j=1;j<=s2.size();j++){ if(s1[i-1]==s2[j-1])d=0; else d=1; int a = dp[i-1][j-1]+d; int b = dp[i][j-1]+1; int c = dp[i-1][j]+1; int m = min(a,min(b,c)); dp[i][j] = m; if(m==a&&d==1)pre[i][j]=0; else if(m==b)pre[i][j]=1; else if(m==c)pre[i][j]=2; } } cout << dp[s1.size()][s2.size()] << endl; int x = s1.size(); int y = s2.size(); while(x!=-1&&y!=-1){ int q = pre[x][y]; if(q==0) cout << "REPLACE "<<x<<" "<<s2[y-1]<<endl; if(q==1) {cout << "INSERT "<<x+1<<" "<<s2[y-1]<<endl;x++;} if(q==2) {cout << "DELETE "<<x<<endl;y++;} x--; y--; } }
RECOMMEND