编辑距离

``ABC CBCD``

``2``

``````#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]);
}
}``````

``````#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;
}
``````