动态规划求解编辑距离II(c++实现)

#include<iostream>
#include<cstring>
using namespace std;
const int N=1010,M=15;
int f[N][N];
int n,m;
char str[N][M];

int edit_distance(char a[],char b[]){
    int la=strlen(a+1),lb=strlen(b+1);
    for(int i=1;i<=lb;i++) f[0][i]=i;
    for(int i=1;i<=la;i++) f[i][0]=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);
            f[i][j]=min(f[i][j],f[i-1][j-1]+(a[i]!=b[j]));
        }
    }

    return f[la][lb];
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s",str[i]+1);
    
    while(m--){
        char s[N];
        int limit;
        int res=0;
        scanf("%s%d",s+1,&limit);
        for(int i=1;i<=n;i++){
            if(edit_distance(str[i],s)<=limit) res++;
        }
        printf("%d\n",res);
    }
    
}