AcWing 899. 基础课二刷之第57题加强巩固 编辑距离*
原题链接
简单
作者:
Snow_raw
,
2021-08-22 15:43:59
,
所有人可见
,
阅读 1277
题目描述
给定 n 个长度不超过 10 的字符串以及 m 次询问,每次询问给出一个字符串和一个操作次数上限。
对于每次询问,请你求出给定的 n 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。
每个对字符串进行的单个字符的插入、删除或替换算作一次操作。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行,每行包含一个字符串,表示给定的字符串。
再接下来 m 行,每行包含一个字符串和一个整数,表示一次询问。
字符串中只包含小写字母,且长度均不超过 10。
输出格式
输出共 m 行,每行输出一个整数作为结果,表示一次询问中满足条件的字符串个数。
数据范围
1≤n,m≤1000,
样例
3 2
abc
acd
bcd
ab 1
acbd 2
输出
1
3
算法
dp
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
const int M=15;
const int INF=2e9;
int n,m;
int f[M][M];
char str1[N][M],str[M];
int edited_distance(char a[],char b[]){
int la=strlen(a+1),lb=strlen(b+1);
for(int i=0;i<=la;i++)for(int j=1;j<=lb;j++)f[i][j]=INF;
for(int i=0;i<=la;i++){
f[i][0]=i;
}
for(int j=1;j<=lb;j++){
f[0][j]=j;
}
for(int i=1;i<=la;i++)for(int j=1;j<=lb;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-1][j-1],f[i][j]);
else f[i][j]=min(f[i-1][j-1]+1,f[i][j]);
}
return f[la][lb];
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>str1[i]+1;
while(m--){
int tm;
cin>>str+1>>tm;
int cnt=0;
for(int i=1;i<=n;i++){
int f=edited_distance(str1[i],str);
if(f<=tm)cnt++;
}
cout<<cnt<<endl;
}
return 0;
}
总结
在最短编辑距离的基础(dp)上加了多次匹配,复杂度是10^2*n(1000)*m(1000)接近于1e8非常大