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

这篇具有很好参考价值的文章主要介绍了【字典树/trie树】实现高效插入和查询字符串的数据结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

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

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

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

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

　　这样，当我们多次插入像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 }