专业的网站设计建设,娱乐公司网站建设价格,wordpress md风格,福州seo网站推广优化编辑距离
题目
给定 n n n个长度不超过 10 10 10 的字符串以及 m m m 次询问#xff0c;每次询问给出一个字符串和一个操作次数上限。
对于每次询问#xff0c;请你求出给定的 n n n个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。
每个…编辑距离
题目
给定 n n n个长度不超过 10 10 10 的字符串以及 m m m 次询问每次询问给出一个字符串和一个操作次数上限。
对于每次询问请你求出给定的 n n n个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。
每个对字符串进行的单个字符的插入、删除或替换算作一次操作。
详见899. 编辑距离 - AcWing题库
输入格式
第一行包含两个整数 n n n和 m m m。
接下来 n n n 行每行包含一个字符串表示给定的字符串。
再接下来 m m m 行每行包含一个字符串和一个整数表示一次询问。
字符串中只包含小写字母且长度均不超过 10 10 10。
输出格式
输出共 m m m行每行输出一个整数作为结果表示一次询问中满足条件的字符串个数。
// input:
3 2
abc
acd
bcd
ab 1
acbd 2
// output:
1
3题解
总的思路就是对于在每次询问中将每个序列的最少编辑距离得出在分别与操作次数上限相比即可
#include iostream
#include cstring
using namespace std;int n, m, f[1005][1005], len_1[1005], len_2, t;
char a[1005][1005], b[1005];int main()
{cin n m;for(int i 1; i n; i){cin a[i];len_1[i] strlen(a[i]); }while(m --){int cnt 0;cin b t;len_2 strlen(b); for(int k 1; k n; k){for(int i 0; i len_1[k]; i) f[i][0] i;for(int j 0; j len_2; j) f[0][j] j;for(int i 1; i len_1[k]; i)for(int j 1; j len_2; j){f[i][j] min(f[i - 1][j] 1, f[i][j - 1] 1);f[i][j] min(f[i][j], f[i - 1][j - 1] (a[k][i - 1] ! b[j - 1]));}if(f[len_1[k]][len_2] t) cnt;}cout cnt endl;}return 0;
}
