【字典树/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结尾的字符串的数量，相当于上图中给每个字符串结尾标记。