【C语言】编辑距离问题【原创技术】.doc

字符串A通过插入、删除、替换字符变成另一个字符串B，操作的次数表示两个字符串的差异。用于计算文本相关性、相似性递归关系两字符串长度为N、M，对1iN，1jM，有l 若ai=bj 则LD(i,j)=LD(i-1,j-1)l 若aibj 则LD(i,j)=Min(LD(i-1,j-1),LD(i-1,j),LD(i,j-1)+1求解例A=GGATCGA，B=GAATTCAGTTA，计算LD(A,B)实现代码如下：（代码一）#include#includeint min(int x,int y,int z) int q; if(xy&xz) q=x; else if(yz&yx) q=y; else q=z; return(q); int LevenshDistance(char strA,char strB)int i,j; int m=strlen(strA)+1;int n=strlen(strB)+1;int L200200;for( i=0;im;i+)L0=i;for( j=0;jn;j+) L0j=j;for(i=1;im;i+)for(j=1;jn;j+)if(strA=strBj) Lj=Li-1j-1;else Lj=min(Li-1j-1,Li-1j,Lj-1)+1;return Lm-1n-1;void main()char a200,b200;gets(a);gets(b);printf(%dn,LevenshDistance(a,b);（代码二）/题目：编辑距离计算算法/作者：武叶/日期：2012年3月28日#include#includeint min_one(int left,int middle,int right) ;int compare_Distance(char strA,char strB);int main() int distance;char a100,b100;gets(a); /输入两组字符串gets(b);distance=compare_Distance(a,b); /调用compare_Distance函数计算编辑距离printf(%dn,distance); return 0;int min_one(int left,int middle,int right) int min_one; if(leftmiddle&leftright) min_one=left; /最右边的是最小的一个else if(middleright&middleleft) min_one=middle; /中间的一个是最小的一个else min_one=left; /右边的是最小的一个 return(min_one); int compare_Distance(char strA,char strB)int i,j; int m=strlen(strA)+1;int n=strlen(strB)+1;int L100100;for( i=0;im;i+) /定义第一行的距离为0到m-1L0=i;for( j=0;jn;j+) /定义第一列的距离为0到n-1L0j=j;for(i=1;im;i+)for(j=1;jn;j+)if(strA=strBj) Lj=Li-1j-1; /两个字符相同就等于上一个的距离。else Lj=min_one(Li-1j-1,Li-1j,Lj-1)+1; /如果两个字符不相同，就是前三个最小的一个的距离。return Lm-1n-1; 运行结果截图： 昨天 21:58 上传下载附件 (23.2 KB)源代码下载： edit_Distance.cpp(682 Bytes, 下载次数: 0)昨天 22:00 上传下载次数: 0edit_Distance (2).cpp(1.44 KB, 下载次数: 0)2 分钟前 上传下载次数: 0【C语言】c语言中引入类的概念【原创技术】 ：