字典树学习笔记

trie 树，即字典树，是一种可以实现 $O(S)$ 的预处理（$S$ 为所有字符串的长度和），$O(N)$（$N$ 为查询的字符串的长度）的查询的数据结构。

举个栗子，对于字符串：$\text{abcd}$、$\text{abd}$、$\text{bcd}$、$\text{efg}$，它的 trie 树如下：

那么，trie 树的建立、查询操作怎么代码实现呢？在此奉上蒟蒻的代码：

• 建立

  int trie[maxn][30],cnt[maxn],tot;
  //trie[N][r]用来存储Trie树中的子节点（节点编号为N，它的字符儿子编号为r，比如trie[2][3]存储的就是节点编号为2，它的一个儿子为'd'）
  //cnt[N]存储的是以当前结尾的字符串有多少个，tot存储当前共有几个节点
  //下标是0的点，既是根节点，又是空节点
  char str[N];
  void insert(char *str)
  {int p=0;//根节点为0for(int i=0;str[i];i++){int u=str[i]-'a';//当前字母子节点if(!trie[p][u]) trie[p][u]=++tot;//如果当前子节点不存在就创造一个点来存储子节点p=trie[p][u];//让p走到子节点的位置cnt[p]++;//结尾是p的字符串个数增加}
  }
  

• 查询

  int query(char *str)
  {int p=0;for(int i=0;str[i];i++){int u=str[i]-'a';//当前字母子节点的编号if(!trie[p][u]) return 0;//如果当前字符不存在那么直接返回0p=trie[p][u];//让p走到子节点的位置}return cnt[p];//最后返回以p结尾的字符串个数
  }
  

---

练手板子题

代码如下：

#include <bits/stdc++.h>
using namespace std;const int maxn=2e6+5;
int t[maxn][65],cnt[maxn],tot;
char s[maxn];int getn(char x)
{if(x<='Z'&&x>='A') return x-'A';else if(x<='z'&&x>='a') return x-'a'+26;else return x-'0'+52;
}void insert(char s[])
{int p=0,len=strlen(s);//根节点为0for(int i=0;i<len;i++){int u=getn(s[i]);//当前字母子节点if(!t[p][u]) t[p][u]=++tot;//如果当前子节点不存在就创造一个点来存储子节点p=t[p][u];//让p走到子节点的位置cnt[p]++;//结尾是p的字符串个数增加}
}int ask(char s[])
{int p=0,len=strlen(s);for(int i=0;i<len;i++){int u=getn(s[i]);if(!t[p][u]) return 0;p=t[p][u];}return cnt[p];
}int main()
{int T;cin>>T;while(T--){for(int i=0;i<tot;i++)for(int j=0;j<65;j++) t[i][j]=0;for(int i=0;i<tot;i++) cnt[i]=0;tot=0;int n,q;cin>>n>>q;for(int i=1;i<=n;i++)cin>>s,insert(s);for(int i=1;i<=q;i++)cin>>s,cout<<ask(s)<<endl;}return 0;
}