其实就是902 最短编辑距离那题的应用

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int n, m;
vector<string> os;  // original string

int dis(string s, int op){
    int dp[11][11], m = s.size(), res = 0;
    for (auto o : os){
        int n = o.size();
        for (int i = 0; i <= n; i ++){
            for (int j = 0; j <= m; j ++){
                if (!i) dp[i][j] = j;
                else if (!j) dp[i][j] = i;
                else{
                    if (o[i - 1] == s[j - 1]) dp[i][j] = dp[i - 1][j - 1];
                    else dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1;
                }
            }
        }
        if (dp[n][m] <= op) res ++;
    }
    return res;
}

int main(){
    cin >> n >> m;
    string s; int op;
    while (n --){
        cin >> s;
        os.push_back(s);
    }
    while (m --){
        cin >> s >> op;
        cout << dis(s, op) << endl;
    }

    return 0;
}