AcWing 899. 编辑距离
原题链接
简单
作者:
sy123
,
2020-12-24 11:03:29
,
所有人可见
,
阅读 323
#include<bits/stdc++.h>
using namespace std;
const int N=15,M=1010;
int f[N][N];
char a[N],b[N];
char str[M][N];
int get(char a[],char b[]){
int n = strlen(a + 1), m = strlen(b + 1);//从第一位开始计算长度
for(int i=0;i<=m;i++)f[0][i]=i;//只能增加
for(int i=0;i<=n;i++)f[i][0]=i;//只能删除
//注意i,j从1开始枚举
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);//删除与增加操作取最小值
//增加操作分成最后一位相等与否讨论
if(a[i]==b[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[n][m];
}
int main(){
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)scanf("%s",str[i]+1);//str+1开始输入,避免很多边界条件
while (m -- )
{
char s[N];
int limit;
scanf("%s%d", s + 1, &limit);
int res=0;
for(int i=0;i<n;i++){ //遍历n个字符串
if(get(str[i],s)<=limit)
res++;
}
cout<<res<<endl;
}
return 0;
}