思路
-
-
按照上面的思路,多次计算编辑距离即可。
- 时间复杂度为 $O(MN \times 10^2)$ 。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
char s[N][12];
int f[12][12];
int main(void){
int n,m;
scanf("%d%d",&n,&m);
int i,j,k1,k2;
for(i=1;i<=n;i++){
scanf("%s",&s[i][1]);
}
for(i=1;i<12;i++){
f[i][0]=i,f[0][i]=i;
}
char t[12];
int d;
for(i=1;i<=m;i++){
int ans=0;
scanf("%s%d",&t[1],&d);
for(j=1;j<=n;j++){
for(k1=1;k1<=strlen(s[j]+1);k1++){
for(k2=1;k2<=strlen(t+1);k2++){
f[k1][k2]=min({f[k1-1][k2],f[k1][k2-1],f[k1-1][k2-1]})+1;
if(s[j][k1]==t[k2]){
f[k1][k2]=min(f[k1][k2],f[k1-1][k2-1]);
}
}
}
//cout<<f[strlen(s[j]+1)][strlen(t+1)]<<endl;
if(f[strlen(s[j]+1)][strlen(t+1)]<=d) ans++;
}
printf("%d\n",ans);
}
return 0;
}