编辑距离
时间： 1ms 内存：64M
描述：
假设字符串的基本操作仅为：删除一个字符、插入一个字符和将一个字符修改成另一个字符这三种操作。
我们把进行了一次上述三种操作的任意一种操作称为进行了一步字符基本操作。
下面我们定义两个字符串的编辑距离：对于两个字符串a和b，通过上述的基本操作，我们可以把a变成b或b变成a，那么字符串a变成字符串b需要的最少基本字符操作步数称为字符串a和字符串b的编辑距离。
例如：a="ABC",b="CBCD",则a与b的编辑距离为2。
你的任务就是：编一个快速的程序来计算任意两个字符串的编辑距离。
输入：
输入包含多组测试数据。每组测试数据一行，为字符串A和字符串B。
字符串的长度不大于1024，且全为字母。
输出：
编辑距离。
示例输入：
ABC CBCD示例输出：
2提示：
参考答案（内存最优[1096]）：
#include<stdio.h>
#include<string.h>
int jie(int a,int b,int c,char yi,char er)
{
int shang=c+1,xia=b+1,zuo=a;
if(yi!=er)
zuo++;
if(shang<=xia&&shang<=zuo)
return shang;
if(xia<=shang&&xia<=zuo)
return xia;
if(zuo<=shang&&zuo<=xia)
return zuo;
}
int main()
{
int a[1034],d[1034],i,j,k;
char b[1034],c[1034],*p,*q;
while(scanf("%s %s",&b,&c)!=EOF)
{
p=b;
q=c;
a[0]=0;
for(i=1;*(q+i-1)!='\0';i++)
{
a[i]=i;
}
for(i=0;*(p+i)!='\0';i++)
{
d[0]=i+1;
for(j=0;*(q+j)!='\0';j++)
{
d[j+1]=jie(a[j],a[j+1],d[j],*(p+i),*(q+j));
}
a[0]=i+1;
for(k=1;*(q+k-1)!='\0';k++)
{
a[k]=d[k];
}
}
printf("%d\n",a[j]);
}
}参考答案（时间最优[152]）：
#include <iostream>
#include <cmath>
#include<string>
#include<algorithm>
#define MAX 1025
using namespace std;
int DP[MAX][MAX];
int min(int a, int b, int c) {
int min = a;
if (b < min)
min = b;
if (c < min)
min = c;
return min;
}
int main() {
string s1, s2;
int len_1, len_2;
while (cin >> s1 >> s2) {
len_1 = s1.size();
len_2 = s2.size();
s1 = ' ' + s1;
s2 = ' ' + s2;
int i, j;
for (i = 0; i <= len_1; i++)
DP[i][0] = i;
for (j = 0; j <= len_2; j++)
DP[0][j] = j;
for (i = 1; i <= len_1; i++)
for (j = 1; j <= len_2; j++)
//计算替换操作的代价，如果两个字符相同，则替换操作代价为0，否则为1
//dp[i-1, j] + 1, //在str1上i位置删除字符（或者在str2上j-1位置插入字符）
//dp[i, j-1] + 1, //在str1上i-1位置插入字符（或者在str2上j位置删除字符）
//dp[i-1, j-1] + 1 // 替换操作
if (s1[i] == s2[j])
DP[i][j] = DP[i - 1][j - 1];
else
DP[i][j] = min(DP[i - 1][j - 1] + 1, DP[i - 1][j] + 1, DP[i][j - 1] + 1);
printf("%d\n", DP[len_1][len_2]);
}
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。