用c++代码实现字典树的模糊搜索

下面是用 C++ 代码实现字典树（Trie）的模糊搜索：

#include <iostream>
#include <vector>
#include <string>
#include <cstring>

using namespace std;

const int MAX_N = 1000005;
const int MAX_M = 10005;
const int MAX_L = 25;

struct TrieNode {
    int son[26];
    bool is_end;
} trie[MAX_N];

int tot = 1;

void insert(string s) {
    int p = 1;
    for (int i = 0; i < s.length(); i++) {
        int c = s[i] - 'a';
        if (!trie[p].son[c]) {
            trie[p].son[c] = ++tot;
        }
        p = trie[p].son[c];
    }
    trie[p].is_end = true;
}

vector<string> ans;

void dfs(int p, string s, int cnt, int k) {
    if (trie[p].is_end && cnt <= k) {
        ans.push_back(s);
    }
    if (cnt > k) {
        return;
    }
    for (int i = 0; i < 26; i++) {
        if (trie[p].son[i]) {
            char c = 'a' + i;
            dfs(trie[p].son[i], s + c, cnt + (c != s[s.length() - 1]), k);
        }
    }
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        insert(s);
    }
    for (int i = 1; i <= m; i++) {
        string s;
        cin >> s;
        ans.clear();
        dfs(1, "", 0, k);
        int cnt = 0;
        for (int j = 0; j < ans.size(); j++) {
            if (ans[j].find(s) != string::npos) {
                cnt++;
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

在这个代码中，`trie` 数组表示字典树，`tot` 表示字典树的节点数量。`insert()` 函数用于将单词插入字典树。`dfs()` 函数用于进行深度优先搜索，其中 `p` 表示当前节点的编号，`s` 表示当前字符串，`cnt` 表示当前编辑距离，`k` 表示最大编辑距离。在 `dfs()` 函数中，如果当前节点是一个单词的结尾，并且编辑距离不超过 `k`，则将当前字符串加入答案数组 `ans` 中。然后遍历当前节点的所有儿子节点，如果某个儿子节点存在，则继续递归搜索。在递归搜索时需要注意，如果当前字符和上一个字符相同，则不需要增加编辑距离，否则需要增加编辑距离。

在主函数中，首先读入字典树中单词的数量 `n`，查询的数量 `m`，以及最大编辑距离 `k`。然后逐个读入查询字符串，对于每个查询字符串，先清空答案数组 `ans`，然后调用 `dfs()` 函数进行搜索。搜索完成后，遍历答案数组 `ans`，如果某个字符串中包含查询字符串，则将计数器 `cnt` 加一。最后输出计数器 `cnt` 即可。