算法基础之编辑距离
2023-12-26 18:43:25
编辑距离
-
核心思想:线性dp 最短编辑距离的应用
-
每次传两个字符串比较 返回最短距离即可
-
#include<iostream> #include<algorithm> #include<string.h> using namespace std; const int N = 15, M =1010; //每个字符串最长15 int f[N][N]; char str[M][N]; int n,m; int edit(char a[],char b[]) { int la = strlen(a + 1) , lb = strlen(b + 1); //算长度 从1开始 //初始化 for(int i =0;i<=la;i++) f[i][0] = i; for(int i =0;i<=lb;i++) f[0][i] = i; for(int i=1;i<=la;i++) { for(int j=1;j<=lb;j++) { f[i][j] = min(f[i-1][j] + 1 , f[i][j-1] + 1); //优化 : a[i] != b[j] f[i][j] = min(f[i][j] , f[i-1][j-1] + (a[i] != b[j]); } } return f[la][lb]; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) scanf("%s", str[i] + 1); //str保存所有字符串 从几开始无所谓 while(m--) { char s[N]; int limit; scanf("%s%d", s + 1,&limit); //传入询问字符串和最大次数 int res = 0; for(int i=1;i<=n;i++) if(edit(str[i],s) <= limit) //返回最短距离 res ++; cout<<res<<endl; } }
-
文章来源:https://blog.csdn.net/Pisasama/article/details/135226870
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!