【C++】【算法基础】序列编辑距离

编辑距离

题目

给定 $n$个长度不超过 $10$ 的字符串以及 $m$ 次询问，每次询问给出一个字符串和一个操作次数上限。

对于每次询问，请你求出给定的$n$个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。

每个对字符串进行的单个字符的插入、删除或替换算作一次操作。

详见899. 编辑距离 - AcWing题库

输入格式

第一行包含两个整数$n$和$m$。

接下来 $n$ 行，每行包含一个字符串，表示给定的字符串。

再接下来 $m$ 行，每行包含一个字符串和一个整数，表示一次询问。

字符串中只包含小写字母，且长度均不超过 $10$。

输出格式

输出共$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;
}