C语言计算2个字符串的编辑距离

C语言计算2个字符串的编辑距离编辑距离：通过插入、删除、替换一个字符(和交换相邻字符)的操作，使得字符串A和字符串B相同，而最少的操作次数就是编辑距离。如字符串abcd和aca的距离是2代码转自：http://blog.csdn.net/wapwo/article/details/8831810

动态规划得到转移状态方程:1.&nbsp&nbspdis(s1,””)&nbsp=&nbspd(“”,s1)&nbsp=&nbsp|s1|&nbsp&nbsp&nbsp&nbspdis(“c1″,”c2”)&nbsp=&nbspc1&nbsp==&nbspc2&nbsp?&nbsp0&nbsp:2.&nbsp&nbspdis(s1+c1,s2+c2)&nbsp=&nbspmin(&nbsp&nbspdis(s1,s2)+&nbspc1==c2&nbsp?&nbsp0&nbsp:&nbsp1&nbsp,&nbsp//替换&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbspdis(s1+c1,s2)+1,&nbsp&nbsp&nbsp&nbsp//s2中插入c1,等价于s1后删除c1&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbspdis(s1,s2+c2)+1&nbsp&nbsp);&nbsp&nbsp&nbsp&nbsp//s2后删除c2,等价于s1中插入c2即：f[i][j]=min{f[i-1][j-1]+c1==c2?0:1,&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbspf[i][j-1]+1,&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbspf[i-1][j]+1}

#include<stdio.h>
#include<string.h>
/*递归计算编辑距离 删除、替换、插入 (i行,j列)*/
int dis(char *s,char *t,int j,int i){
	int a,b,c,min;
	if(i>0 && j>0){
		a=t[i-1]==s[j-1]?dis(s,t,j-1,i-1):dis(s,t,j-1,i-1)+1;
		b=dis(s,t,j,i-1)+1;
		c=dis(s,t,j-1,i)+1;	
		min=a>b?b:a;
		return min>c?c:min;
	}else if(i==0 && j==0){
		return t[0]==s[0]?0:1;
	}else if(i==0){
		return j;
	}else if(j==0){
		return i;
	}
}
void main(){
	char *s="acdx";
	char *t="acxx";
	printf("\n\n%s和%s之间的距离为：%d\n\n",s,t,dis(s,t,strlen(s),strlen(t)));
}