AcWing 899. 编辑距离
原题链接
简单
作者:
AC_
,
2021-01-28 22:16:52
,
所有人可见
,
阅读 365
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX = 1e3 + 10;
int m, n;
char a[MAX][12];
char b[12];
int op;
int f[12][12];
int main()
{
scanf("%d %d", &m, &n);
for (int i = 0; i < m; i ++) scanf("%s", a[i] + 1);
for (int i = 0; i < 12; i ++) f[0][i] = f[i][0] = i;
for (int t = 0; t < n; t ++) {
for (int x = 0; x < 12; x ++) b[x] = 0;
scanf("%s%d", b + 1, &op);
int ans = 0;
for (int k = 0; k < m; k ++) {
int len1 = strlen(b + 1);
int len2 = strlen(a[k] + 1);
for (int i = 1; i <= len1; i ++) {
for (int j = 1; j <= len2; j ++) {
f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
if (b[i] == a[k][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);
}
}
if (f[len1][len2] <= op) ++ans;
}
printf("%d\n", ans);
}
return 0;
}