主题链接：
编辑距离。，== 一边dp虽然录制前体累，，依然是dp
#include#include #include #include using namespace std;#define ll int#define N 1010char s[N], t[N];int dp[N][N], n, m;// 0为插入 1为删除 2 3为替换struct node{ int op; int pos; char c; node(int A=0,int E=0,char D=0):op(A),pos(E), c(D){} void put(){ if(op== 2) printf("REPLACE %d %c\n", pos, c); else if(op == 0) printf("INSERT %d %c\n", pos +1, c); else if(op == 1) printf("DELETE %d\n", pos); }}P;void dfs(int a, int b){ if(a == 0 && b==0)return ; if(s[a] == t[b] && dp[a-1][b-1] == dp[a][b]) dfs(a-1, b-1); else { if(a && dp[a-1][b] +1 == dp[a][b]) { P = node(1, a); P.put(); dfs(a-1, b); } else if(b && dp[a][b-1] +1 == dp[a][b]) { P = node(0, a, t[b]); P.put(); dfs(a, b-1); } else if(a && b && dp[a-1][b-1] +1 == dp[a][b]) { P = node(2, a, t[b]); P.put(); dfs(a-1, b-1); } }}void input(){ scanf("%s", t+1); n = strlen(s+1); m = strlen(t+1);}int main(){ int i, j; while(~scanf("%s", s+1)){ input(); dp[0][0] = 0; for(i = 1; i <= n; i++) dp[i][0] = i; for(i = 1; i <= m; i++) dp[0][i] = i; for(i = 1; i <= n; i++) for(j = 1; j <= m; j++) dp[i][j] = min(min(dp[i-1][j], dp[i][j-1])+1, dp[i-1][j-1] + (s[i]!=t[j])); printf("%d\n", dp[n][m]); dfs(n, m); } return 0;}
版权声明：本文博客原创文章，博客，未经同意，不得转载。