#define maxNum 100
char a[maxNum],b[maxNum];//存放输入字符串
int c[maxNum][maxNum];//动态规划二维表
int diff(char a,char b)//判断字符a,b是否相等, 相等则编辑距离不增加,返回0,否则返回1
{
if(a==b)
return 0;
else
return 1;
}
int min(int a,int b,int c)//求三数中最小的
{
int d;
if(a<b)
d=a;
else
d=b;
if(c<d)
return c;
else
return d;
}
int main()
{
printf("please input string a/n");
scanf("%s",a);
printf("please input string b/n");
scanf("%s",b);
printf("%s %s/n",a,b);
int len_a=strlen(a);
int len_b=strlen(b);
int i,j;
for(i=0;i<=len_a;i++)
c[i][0]=i;
for(j=0;j<=len_b;j++)
c[0][j]=j;
for(i=1;i<=len_a;i++)
for(j=1;j<=len_b;j++)
c[i][j]=min(1+c[i-1][j],1+c[i][j-1],diff(a[i-1],b[j-1])+c[i-1][j-1]);
for(i=0;i<=len_a;i++)
{
for(j=0;j<=len_b;j++)
cout<<c[i][j]<<" ";
cout<<endl;
}
system("pause");
return 0;
}
/*
please input string a
EXPONENTIAL
please input string b
POLYNOMIAL
EXPONENTIAL POLYNOMIAL
0 1 2 3 4 5 6 7 8 9 10
1 1 2 3 4 5 6 7 8 9 10
2 2 2 3 4 5 6 7 8 9 10
3 2 3 3 4 5 6 7 8 9 10
4 3 2 3 4 5 5 6 7 8 9
5 4 3 3 4 4 5 6 7 8 9
6 5 4 4 4 5 5 6 7 8 9
7 6 5 5 5 4 5 6 7 8 9
8 7 6 6 6 5 5 6 7 8 9
9 8 7 7 7 6 6 6 6 7 8
10 9 8 8 8 7 7 7 7 6 7
11 10 9 8 9 8 8 8 8 7 6
请按任意键继续. . .
*/