编辑距离

注意：涉及dp字符串，读入时常从下标1读入，便于后期操作

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string.h>
using namespace std;
const int N = 20, M = 1010;
int f[N][N];
char str[M][N]; 
int n,m;
int  check(char str[],char s[])  //和最短遍历距离一样
{
    int n1=strlen(str+1),n2=strlen(s+1);
    for (int j=0;j<=n2;j++) f[0][j]=j;
    for (int i=0;i<=n1;i++) f[i][0]=i;
    for (int i=1;i<=n1;i++)
        for (int j=1;j<=n2;j++)
        {
            f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
            if (str[i]==s[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[n1][n2];
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=0;i<n;i++) scanf("%s",str[i]+1);  //注意读入，每行读入的字符串从1开始
    while (m--)  //m个询问
    {
        char s[N],limit;  //读入询问的字符串和限制的操作次数
        scanf("%s%d",s+1,&limit);
        int ans=0;  //统计符合条件的字符串的个数
        for (int i=0;i<n;i++)  //遍历n个已知的字符串求答案
        {
            if (check(str[i],s)<=limit) ans++;  
        }
        printf("%d\n",ans);
    }
    return 0;
}