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

  本文是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结尾的字符串的数量,相当于上图中给每个字符串结尾标记。

热门相关:天河大帝   天河大帝   官策   诛明   抗日之特战兵王