11.编辑距离

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 15, M = 1010;
 4 int n, m;
 5 char str[M][N];
 6 int dp[N][N];
 7 int edit_distance(char str[], char s[]) {
 8     int la = strlen(str + 1), lb = strlen(s + 1);
 9     for (int i = 0; i <= lb; i++) {
10         dp[0][i] = i;
11     }
12     for (int i = 0; i <= la; i++) {
13         dp[i][0] = i;
14     }
15     for (int i = 1; i <= la; i++) {
16         for (int j = 1; j <= lb; j++) {
17             dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
18             dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (str[i] != s[j]));
19         }
20     }
21     return dp[la][lb];
22 }
23 int main() {
24     cin >> n >> m;
25     for (int i = 1; i <= n; i++) {
26         cin >> str[i] + 1;
27     }
28     while (m--) {
29         char s[N];
30         int limit;
31         cin >> s + 1 >> limit;
32         int cnt = 0;
33         for (int i = 1; i <= n; i++) {
34             if (edit_distance(str[i], s) <= limit) {
35                 cnt++;
36             }
37         }
38         cout << cnt << endl;
39     }
40     return 0;
41 }