题目描述

给定 n 个长度不超过 10 的字符串以及 m 次询问，每次询问给出一个字符串和一个操作次数上限。
对于每次询问，请你求出给定的 n 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。
每个对字符串进行的单个字符的插入、删除或替换算作一次操作。

样例

输入样例：
3 2
abc
acd
bcd
ab 1
acbd 2
输出样例：
1
3

时间复杂度O(nm)

#include<iostream>
#include<cstring>
using namespace std;
const int N=1010;
int f[N][N];
char str[N][12];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%s",str[i]+1);//注意从1开始读入
    for(int i=1;i<N;i++)
    {
        f[i][0]=i;
        f[0][i]=i;
    }//初始化
    while(m--)
    {
        char s[12];
        int t;
        scanf("%s%d",s+1,&t);
        int res=0;
        for(int k=1;k<=n;k++)
        {
            int la=strlen(str[k]+1),lb=strlen(s+1);
            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);
                    if(str[k][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);
                }
            }
            if(f[la][lb]<=t)res++;
        }
        cout<<res<<endl;
    }
    return 0;
}