AcWing 899. 编辑距离
原题链接
简单
作者:
晓龙coding
,
2021-08-27 11:17:04
,
所有人可见
,
阅读 95
#include<iostream>
#include<string>
using namespace std;
const int N = 1010;
string ch[N];
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> ch[i];
}
while (m--) {
string str = "";
int cnt = 0, ans = 0;
cin >> str >> cnt;
for (int i = 0; i < n; i++) { //n个字符串
int f[N][N];
int m = ch[i].size();
for (int j = 0; j <= m; j++) f[j][0] = j;
for (int k = 0; k <= str.size(); k++) f[0][k] = k;
for (int j = 1; j <= m; j++) {
for (int k = 1; k <= str.size(); k++) {
f[j][k] = min(f[j - 1][k], f[j][k - 1]) + 1;
f[j][k] = min(f[j][k], f[j - 1][k - 1] + (ch[i][j - 1] != str[k - 1]));
}
}
if (f[m][str.size()] <= cnt) ans++;
}
cout << ans << endl;
}
return 0;
}