给定 n 个长度不超过 1010 的字符串以及 m 次询问，每次询问给出一个字符串和一个操作次数上限。
对于每次询问，请你求出给定的 n 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。
每个对字符串进行的单个字符的插入、删除或替换算作一次操作。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行，每行包含一个字符串，表示给定的字符串。
再接下来 m 行，每行包含一个字符串和一个整数，表示一次询问。
字符串中只包含小写字母，且长度均不超过 10。
输出格式
输出共 m 行，每行输出一个整数作为结果，表示一次询问中满足条件的字符串个数。
数据范围
1≤n,m≤1000
输入样例：
1. 3 2 2. abc 3. acd 4. bcd 5. ab 1 6. acbd 2
输出样例：
1. 1 2. 3
思路可以看上面这篇：
#include<iostream> #include<string.h> using namespace std; const int N=15,M=1010; int f[N][N],x; char str[M][N],a[N]; int main(){ //输入 int n,m; cin>>n>>m; for(int i=1;i<=n;i++){ cin>>str[i]+1; } //询问 while(m--){ cin>>a+1>>x; int res=0; //遍历每个字符串 for(int i=1;i<=n;i++){ int la=strlen(str[i]+1),lb=strlen(a+1);//获取字符串长度 //边界初始化 for(int j=1;j<=la;j++) f[j][0]=j; for(int j=1;j<=lb;j++) f[0][j]=j; //DP for(int j=1;j<=la;j++){ for(int k=1;k<=lb;k++){ f[j][k]=min(f[j-1][k]+1,f[j][k-1]+1); //f[i][j]每次会被f[i-1][j]与f[i][j-1]无条件覆盖，最开始会被f[1][0]与f[0][1]覆盖，因为边界初始化了，内部就会无条件跟着初始化 if(str[i][j]==a[k]) f[j][k]=min(f[j][k],f[j-1][k-1]); else f[j][k]=min(f[j][k],f[j-1][k-1]+1); } } // 判断是否符合limit if(f[la][lb]<=x) res++; } cout << res <<endl ; } return 0; }
