首页 > 代码库 > Codeforces 56D Changing a String 编辑距离 dp
Codeforces 56D Changing a String 编辑距离 dp
题目链接:点击打开链接
编辑距离,,== 一边dp一边记录前驱太累,,还是dp后找路径大法好
#include<iostream> #include<cstdio> #include<vector> #include<string.h> using namespace std; #define ll int #define N 1010 char 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。