首页 > 代码库 > UVa 164 - String Computer
UVa 164 - String Computer
题目:编辑距离,给你两个串,将已知串转化成目标串,可以增、删、改字母,求最小操作次数。
分析:dp,编辑距离。同最大公共子序列。注意操作位置是实时变化的。(前面都已经处理好了)
f[i][j] = f[i-1][j] 这时删掉 str1[i],位置j+1;
f[i][j] = f[i][j-1] 这时增加 str2[j],位置j;
f[i][j] = f[i-1][j-1]+k 如果str1[i] == str2[j]这时相同k=0,否则k=1,位置j。
说明:注意是str1变成str2;变化位置是这一步时所在的位置(前面的都处理过了)。
#include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> char str1[24],str2[24]; int dp[24][24],op[24][24]; void output( int i, int j ) { if ( !i && !j ) return; if ( op[i][j] == 1 ) { output( i-1, j ); printf("D%c%02d",str1[i-1],j+1); }else if ( op[i][j] == 2 ) { output( i, j-1 ); printf("I%c%02d",str2[j-1],j); }else if ( op[i][j] == 3 ){ output( i-1, j-1 ); printf("C%c%02d",str2[j-1],j); }else output( i-1, j-1 ); } int main() { while ( scanf("%s",str1) && str1[0] != '#' ) { scanf("%s",str2); int l1 = strlen(str1); int l2 = strlen(str2); for ( int i = 0 ; i <= l1 ; ++ i ) for ( int j = 0 ; j <= l2 ; ++ j ) { dp[i][j] = 400; op[i][j] = 0; } //初始化 for ( int i = 0 ; i <= l1 ; ++ i ) { op[i][0] = 1; dp[i][0] = i; } for ( int i = 0 ; i <= l2 ; ++ i ) { op[0][i] = 2; dp[0][i] = i; } for ( int i = 1 ; i <= l1 ; ++ i ) for ( int j = 1 ; j <= l2 ; ++ j ) { if ( str1[i-1] != str2[j-1] ) { op[i][j] = 3; dp[i][j] = dp[i-1][j-1]+1; }else dp[i][j] = dp[i-1][j-1]; if ( dp[i-1][j]+1 < dp[i][j] ) { op[i][j] = 1; dp[i][j] = dp[i-1][j]+1; } if ( dp[i][j-1]+1 < dp[i][j] ) { op[i][j] = 2; dp[i][j] = dp[i][j-1]+1; } } output( l1, l2 ); printf("E\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。