题目

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

输入格式

第一行包含两个整数 n 和 m。
接下来 n 行，每行包含一个字符串，表示给定的字符串。
再接下来 m 行，每行包含一个字符串和一个整数，表示一次询问。
字符串中只包含小写字母，且长度均不超过 10。

输出格式

输出共 m 行，每行输出一个整数作为结果，表示一次询问中满足条件的字符串个数。

数据范围

1 <= n <= 10, m <= 1000

下述代码包含了所有代码细节的解读 本题题解不作细致的单栏解析

代码

#include <iostream>
#include <string.h>
#include <algorithm>

using namespace std;
//n不超过10个，询问不超过1000
const int N = 15,M = 1010;
//n个字符串 m个询问
int n,m;
//dp数组f[i][j] 表示 a[]字符串前i个字符和b[]字符串前j个字符 最短编辑距离
int f[N][N];
//s1字符串数组用于存储 参与到匹配的所有字符串
//最多存M个询问数组，N为最大长度限制
char s1[M][N];

int edit_dis(char a[],char b[])
{
    //strlen是string.h内的函数 用于计算字符串数组大小
    int la = strlen(a + 1),lb = strlen(b + 1);
    //dp初始化 初始化a数组b数组在一方为0的情况下需要多少编辑距离
    for(int i = 0;i <= la;i++) f[i][0] = i;
    for(int i = 0;i <= lb;i++) f[0][i] = i;
    //dp过程
    for(int i = 1;i <= la;i++)
    {
        for(int j = 1;j <= lb;j++)
        {
            //情况一和二先做min
            //1.a增加一个字符到b，反之亦然
            //2.b减少一个字符到a，反之亦然
            f[i][j] = min(f[i - 1][j] + 1,f[i][j - 1] + 1);
            //对情况一和二min之后，还需要对字符长度相同的两个数组做判断
            //若末尾的两个数字不同还需要额外加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);
    //首先读入n个字符串 s1[i]+1的位置开始存放数组
    for(int i = 0;i < n;i++) scanf("%s",s1[i] + 1);
    //m个询问
    while(m--)
    {
        //每一次存放询问字符串的数组
        char s2[N];
        //限制数
        int limit;
        //每一次质询 读入字符串和限制数
        scanf("%s%d",s2 + 1,&limit);
        //满足限制的答案数
        int res = 0;
        for(int i = 0;i < n;i++)
        {
            //遍历所有给定的字符串与质询字符串作最小编辑距离计算
            if(edit_dis(s1[i],s2) <= limit) res++;
        }
        //一次质询输出一次换行的答案
        printf("%d\n",res);
    }
    return 0;
}