首页 > 代码库 > 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;
}