AcWing 899. 编辑距离
原题链接
简单
作者:
叶北辰
,
2023-02-10 17:48:50
,
所有人可见
,
阅读 144
C++ 代码
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=1010,M=15;
char str[N][N];
int f[N][N];//f[i][j] 表示 a[1~i] 转换成 b[1~j] 的最少操作数
int n,m;
int lookup(char* ls,char *s)
{
//获取长度
int lss=strlen(ls+1);
int rs=strlen(s+1);
for(int i=0;i<=lss;i++)//删除操作
f[i][0]=i;/*当j为0的时候,将字符串删除完的个数吗,等于字符串的长度
*/
for(int i=0;i<=rs;i++)//插入操作
f[0][i]=i;/*当i为0的时候,插入的字符的个数取决于访问字符串的长度
*/
//下标从一开始,防止越界
for(int i=1;i<=lss;i++)
{
for(int j=1;j<=rs;j++)
{
f[i][j]=min(min(f[i-1][j],f[i][j-1])+1,f[i-1][j-1]+(ls[i]!=s[j]));
/*之所以删除操作是f[i-1][j],而插入操作是f[i][j-1],因为删除之后上一次已经访问下标是i-1
而j是没有动的,同样,插入操作的f[i][j-1],j是ls字符串插入之后,而j的位置不匹配,就要返回
上一次的位置,就是j-1,而在i的后面插入,i本身没有变化,f[i-1][j-1]+(ls[i]!=s[j])
是上一次已经匹配的部分加上这一次的结果从而得到的操作次数数据*/
}
}
return f[lss][rs];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%s",str[i]+1);
}
for(int j=0;j<m;j++)
{
char st[N];
int limit;
scanf("%s%d",st+1,&limit);
//定义长度开始查找
int rez=0;
for(int i=0;i<n;i++)
{
if(lookup(str[i],st)<=limit)
rez++;
}
printf("%d\n",rez);
}
return 0;
}