(dp) acwing 899. Edit distance

899. Edit distance

Topic link https://www.acwing.com/problem/content/901/
subject ：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;
char a[1010][15];
int n,m;
int f[15][15];
int pd(char s[],char c[]){
    
    int lens=strlen(s+1);
    int lenc=strlen(c+1);
    for(int i=0;i<=lens;i++) f[i][0]=i;
    for(int i=0;i<=lenc;i++) f[0][i]=i;
    for(int i=1;i<=lens;i++){
    
        for(int j=1;j<=lenc;j++){
    
            f[i][j]=min(f[i][j-1]+1,f[i-1][j]+1);
            if(s[i]==c[j]) f[i][j]=min(f[i][j],f[i-1][j-1]);
            else f[i][j]=min(f[i][j],f[i-1][j-1]+1);
        }
    }
    return f[lens][lenc];
}
int main(){
    
    cin>>n>>m;
    for(int i=0;i<n;i++){
    
        scanf("%s",a[i]+1);
    }
    int k;
    char s[15];
    while(m--){
    
        scanf("%s%d",s+1,&k);
        int ans=0;
        for(int i=0;i<n;i++){
    
            memset(f,0x3f,sizeof f);
            if(pd(s,a[i])<=k) ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}