编辑距离(Edit Distance)

时间:2022-03-20 09:16:23

Edit Distance
 1000(ms)
 65535(kb)
 568 / 2526

设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符串B。这里所说的字符操作包括 (1)删除一个字符; (2)插入一个字符; (3)将一个字符改为另一个字符。 将字符串A变换为字符串B 所用的最少字符操作数称为字符串A到B 的编辑距离,记为d(A,B)。试设计一个有效算法,对任给的2 个字符串A和B,计算出它们的编辑距离d(A,B)。

输入

 
  

第一行是字符串A,文件的第二行是字符串B。字符串长度不大于2000。

输出

 
  

输出距离d(A,B)

样例输入

fxpimu
xwr

样例输出

5

题解:设dp[i][j]表示第一个字符串0-i子串与第二个字符串0-j子串的最短编辑距离

dp[0][j]:当i=0时相当于,第一个字符串为空,第二个字符串长度为j,此时相当于给第一个字符串字符。

dp[i][0]:当j=0时相当于,第一个字符串长度为i,第二个字符串长度为0,此时相当于给第一个字符串字符。

dp[i][j]:i>0,j>0时,有dp[i][j] = min(dp[i - 1][j]+1, min(dp[i][j - 1]+1, dp[i - 1][j - 1] + (!(str1[i-1] == str2[j-1]))));

此时对于dp[i][j]可以由dp[i - 1][j]+1(第一个字符串加一个字符),dp[i][j - 1]+1(第一个字符串删除一个字符),dp[i - 1][j - 1] +flag(第一个字符串修改一个字符)取最小得到。

#include<iostream>
#include<stdio.h>
#include<queue>
#include<string>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long int
#define getl(str) strlen(str)
#define M(dp,a) memset(dp,sizeof(dp),a)
int dp[2005][2005];
int main()
{
	char sa[2005], sb[2005];
	while (cin >> sa >> sb) {
		M(dp, 0);
		int len1 = getl(sa);
		int len2 = getl(sb);
		for (int i = 0;i <= len1;i++) {
			for (int j = 0;j <= len2;j++) {
				if (i == 0)dp[i][j] = j;
				else if(j==0)dp[i][j] = i;
				else dp[i][j] = min(dp[i - 1][j]+1, min(dp[i][j - 1]+1, dp[i - 1][j - 1] + (!(sa[i-1] == sb[j-1]))));
			}
		}
		cout << dp[len1][len2] << endl;
	}
	return 0;
}