算法基础之编辑距离

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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。