C++实现一个字典树，支持动态添加词汇

和查询词汇是否存在。

字典树是一种树形数据结构，常用于存储字符串，并且支持快速查询字符串是否存在。

实现字典树的方法有很多，一种常用的方法是使用一个数组来表示每个节点的子节点，并且使用一个布尔值来表示该节点是否是一个单词的结尾。

举个例子，如果我们要动态添加字符串"hello"，那么我们可以从根节点开始，每遇到一个字符，就在当前节点的子节点中查找是否有对应的字符，如果没有，就新建一个节点，并将当前节点的指针指向新建的节点。当遍历完字符串"hello"后，最后一个节点的布尔值设为true，表示它是一个单词的结尾。

查询字符串是否存在，我们可以从根节点开始，每遇到一个字符，就在当前节点的子节点中查找是否有对应的字符，如果没有，说明该字符串不存在，否则继续遍历下一个字符。当遍历完所有字符后，如果最后一个节点的布尔值为true，说明该字符串存在，否则说明该字符串不存在。

相关问题

使用c++写一个字典树程序

以下是使用C++编写的一个字典树程序：

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1000005;  // 字典树最大节点数
const int MAXM = 26;  // 字符集大小

struct TrieNode {
    int ch[MAXM];  // 子节点数组
    int val;  // 节点权值
} trie[MAXN];

int root;  // 根节点
int tot = 0;  // 当前节点总数

// 插入一个字符串
void insert(char* s) {
    int len = strlen(s);
    int u = root;
    for (int i = 0; i < len; i++) {
        int c = s[i] - 'a';
        if (!trie[u].ch[c]) {
            trie[u].ch[c] = ++tot;
        }
        u = trie[u].ch[c];
    }
    trie[u].val++;  // 末尾节点权值加1
}

// 搜索一个字符串
int search(char* s) {
    int len = strlen(s);
    int u = root;
    for (int i = 0; i < len; i++) {
        int c = s[i] - 'a';
        if (!trie[u].ch[c]) {
            return 0;  // 没有找到
        }
        u = trie[u].ch[c];
    }
    return trie[u].val;  // 返回末尾节点权值
}

int main() {
    root = tot = 0;  // 初始化根节点和节点总数
    char s[105];
    while (cin >> s) {
        if (s[0] == '#') {
            break;
        }
        insert(s);
    }
    while (cin >> s) {
        if (s[0] == '#') {
            break;
        }
        cout << search(s) << endl;
    }
    return 0;
}

该程序实现了一个简单的字典树，可以进行单词的插入和搜索。其中，`trie`数组表示字典树的节点，每个节点有一个子节点数组`ch`和一个权值`val`，`root`表示字典树的根节点，`tot`表示当前节点总数。程序中的`insert`函数实现了单词的插入，`search`函数实现了单词的搜索。

在使用字典树时，主要的操作就是插入和搜索。插入操作是将单词的每个字符依次加入字典树中，如果该字符的子节点不存在，则新建一个节点。搜索操作是将单词的每个字符依次搜索字典树，如果搜索到某个节点不存在，则说明该单词不存在于字典树中。最后，返回末尾节点的权值即可。

字典树是一种非常实用的数据结构，可以用于解决许多字符串操作问题。在实际应用中，我们可以根据具体的问题需求，对字典树进行一些扩展和优化。

用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` 即可。