算法基础之编辑距离

编辑距离

• 核心思想：线性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;
          }
      }