算法--编辑距离问题

电玩女神 2022-12-21 02:25 160阅读 0赞

![在这里插入图片描述][20201113164317331.png_pic_center]  
该动态规划方程借鉴博客  
[https://www.cnblogs.com/littlepanpc/p/7895810.html][https_www.cnblogs.com_littlepanpc_p_7895810.html]

代码如下：

#include<stdio.h>
    #include<string.h>
    //将A转换为B所用的最少字符操作数称为A到B的编辑距离，记为Shortest_Distance[A][B]
    char a[100];
    char b[100];
    int Shortest_Distance[100][100];
    
    int Edit_distance(int m,int n){ 
    	int p;
    	int q;
    	int r;
    	//第一种情况：两个字符串都是空字符串
    	if(m==-1&&n==-1){ 
    		return 0;
    	}
    	//第二种情况：有一个字符串为空
    	if(m==-1&&n!=-1){ 
    		return n+1;
    	}else if(m!=-1&&n==-1){ 
    		return m+1;
    	}
    	//第三种情况：两个字符串都不为空，找最短距离
    	if(m!=-1&&n!=-1){ 
    		int flag=1;
    		if(a[m]==b[n]){ 
    			flag=0;
    		}
    		p=Edit_distance(m-1,n)+1;
    		q=Edit_distance(m,n-1)+1;
    		r=Edit_distance(m-1,n-1)+flag;
    		if(p<q&&p<r){ 
    			return p;   //这是对A字符串的末尾进行删除，从而使得AB字符串末尾的字符相等 
    		}else if(p>q&&q<r){ 
    			return q;   //这是在A字符串的末尾增加字符，从而使得AB字符串末尾的字符相等
    		}else if(p>r&&q>r){ 
    			return r;   //这是对A字符串的末尾进行修改，从而使得AB字符串末尾的字符相等 
    		}
    	}
    }
    
    int main(){ 
    	gets(a);
    	gets(b);
    	int len_a=strlen(a);
    	int len_b=strlen(b);
    	int sss=Edit_distance(len_a-1,len_b-1);
    	printf("%d",sss);
    	return 0;
    }

[20201113164317331.png_pic_center]: /images/20221120/9ecf39e0bafc49db9028dfe73e2bad34.png
[https_www.cnblogs.com_littlepanpc_p_7895810.html]: https://www.cnblogs.com/littlepanpc/p/7895810.html