Trie 树

Trie 树是一种可以快速查找一个字符串是不是在目前集合中的一个数据结构。

Trie 树的中文名是字典树，顾名思义，这个数据结构就是一个长得像字典的树。

思路

​

上面这个图就是一个 Trie 树，这种树是一个有根树。这种数据结构中，我们不再把每个字符串完全分开存储，而是把相同的合并了。

插入

我们从根节点开始，检查根节点的边有没有符合字符串的，如果没有，就新建一条边。然后，从那条边连接的点开始，重复以上操作，就完成了

查找

和插入类似，从根节点开始查找，如果发现没有对应的边，那么就肯定是没有了。

代码

​

#include <bits/stdc++.h>

using namespace std;
/*
*/
int n;
string s[10005];
int tr[1000005][30];
int cnt=  0;
void insert(string s) {
    int p = 0;
    for (char ch : s) {

        if (tr[p][ch - 'A'] <= 0) {
            tr[p][ch - 'A'] = ++ cnt;
        }
        // cout << ch << " " << s << " " << p << " " << cnt << " " << tr[p][ch - 'A'] << "\n";
        // cout << p << '\n';
        p = tr[p][ch - 'A'];
    }
}
int maxn = -1e9;
void dfs(int nw, int dep) {
    if (nw == -1) {
        maxn = max(dep, maxn);
        return;
    }
    // cout << nw << " " << dep << "\n";
    for (int i = 0; i <= 26; i ++) {
        // if (tr[nw][i]) {
            dfs(tr[nw][i], dep + 1);
        // }
    }

}
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    memset(tr, -1, sizeof(tr));
    while (cin >> s[n + 1]) n ++;
    for (int i = 1; i <= n; i ++) {
        s[i] = char('A' + 27) + s[i];
        insert(s[i]);
    }
    cout << cnt;
    return 0;
}