【字典树/trie树】实现高效插入和查询字符串的数据结构

标签：结点 idx trie son int str 数据结构 id 字典

　　本文是https://www.acwing.com/problem/content/description/837/的总结，有兴趣可以做做

　　字典树的实现依赖于树结构，有两种操作，1是插入字符串，2是查找字符串。使用idx维护最新的结点下标。如下图，假设我们维护一个

 　　可以看到，我们维护了一个树形结构储存了左边的字符串，但是我们不止建立这样的树，还得标记每个字符串的结尾

 　　这样，当我们多次插入像ab这样的字符串的时候就可以记录下插入的总数。我们将每个结点都标记一个编号，根结点标记为0，起全局变量idx实现。具体代码实现如下：

 1 #include<bits/stdc++.h>
 2 #define int long long
 3 using namespace std;
 4 const int INF = 1e18 + 10,maxn = 1e5 + 10;
 5 
 6 int n;
 7 int son[maxn][26],idx,cnt[maxn];
 8 
 9 void insert(char str[]){
10     int p = 0;
11     for(int i = 0; str[i] ; i++){
12         int id = str[i] - 'a';
13         if(!son[p][id]) son[p][id] = ++idx;
14         p = son[p][id];
15     }
16     cnt[p]++;
17 }
18 
19 int quary(char str[]){
20     int p = 0;
21     for(int i = 0; str[i]; i++){
22         int id = str[i] - 'a';
23         if(!son[p][id]) return 0;
24         p = son[p][id];
25     }
26     return cnt[p];
27 }
28 signed main (){
29     ios::sync_with_stdio(false);
30     cin.tie(0),cout.tie(0);
31     
32     cin>>n;
33     char str[maxn];
34     for(int i = 1; i <= n; i++){
35         char op;
36         cin>>op;
37         cin>>str;
38         if(op == 'I'){
39             insert(str);
40         }else if(op == 'Q'){
41             cout << quary(str) << '\n';
42         }
43     }
44     
45     return 0;
46 }

　　在这里解释以下数据结构作用

　　son[i][id]//表示结点i的儿子id是否存在。（还记得吗，我们使用idx给每个结点编号） 　　idx//当更新结点时++idx，赋予新建立的结点独一无二的编号。
　　cnt[i]//表示以结点i结尾的字符串的数量，相当于上图中给每个字符串结尾标记。

标签：结点,idx,trie,son,int,str,数据结构,id,字典
From： https://www.cnblogs.com/jiangjlon/p/17956359