字典树
字典树(Trie)简介
又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
——百度百科
字典树是一种树形结构，用于用于统计，排序和保存大量的字符串。
\(\qquad\qquad\qquad\qquad\qquad\qquad\qquad\)
字典树概念
假设现在有六个字符串，分别是：“ac”、“ace”、“acu”、“wa”、“who”、“pc”，用这几个字符串构造Trie
\(\qquad\qquad\qquad\qquad\qquad\qquad\qquad\)
字典树的运作（图解）
1.插入(建树)
插入字符串的思路很简单，假设现在我们要在一棵空Trie中按顺序插入“ac”、“ace”、“acu”、“wa”、“who”、“pc”
0.插入前
\(\qquad\qquad\qquad\qquad\qquad\qquad\qquad\)
1. 插入“ac”
我们发现当前节点(root)没有“a”，于是新建一个节点“a”；同样的，我们也在“a”下新建一个节点“c”，“c”标记为灰色
\(\qquad\qquad\qquad\qquad\qquad\qquad\qquad\)
2. 插入“ace”
我们发现当前节点(root)有“a”，于是经过节点“a”；同样的，我们也经过“a”节点“c”，“c”标记为灰色；我们发现当前节点(“c”)没有“e”，于是新建一个节点“e”，“e”标记为灰色
\(\qquad\qquad\qquad\qquad\qquad\qquad\qquad\)
3. 插入“acu”
我们发现当前节点(root)有“a”，于是经过节点“a”；同样的，我们也经过“a”节点“c”，“c”标记为灰色；我们发现当前节点(“c”)没有“u”，于是新建一个节点“u”，“u”标记为灰色
\(\qquad\qquad\qquad\qquad\qquad\qquad\qquad\)
4. 插入“wa”
我们发现当前节点(root)没有“w”，于是新建一个节点“w”；同样的，我们也在“w”下新建一个节点“a”，“a”标记为灰色
\(\qquad\qquad\qquad\qquad\qquad\qquad\qquad\)
5. 插入“who”
我们发现当前节点(root)有“w”，于是经过节点“w”；我们发现当前节点(“w”)没有“h”，于是新建一个节点“h”；同样的，我们发现当前节点(“w”)没有“o”，于是也新建一个节点“o”，“o”标记为灰色
\(\qquad\qquad\qquad\qquad\qquad\qquad\qquad\)
6. 插入“pc”
我们发现当前节点(root)没有“p”，于是新建一个节点“p”；同样的，我们也在“p”下新建一个节点“c”，“c”标记为灰色
\(\qquad\qquad\qquad\qquad\qquad\qquad\qquad\)
全程
\(\qquad\qquad\qquad\qquad\qquad\qquad\qquad\)
2.查找
- 假设我们要查找“acu”这个字符串，我们需要顺着树边往下找
\(\qquad\qquad\qquad\qquad\qquad\qquad\)
如果最终的那个点是灰色（该节点是一个字符串结束的位置），查找就完成了，该字符串存在
- 再假设我们要查找“what”这个字符串
\(\qquad\qquad\qquad\qquad\qquad\qquad\)
当找到“a”时，发现没有“a”,这时可以直接返回没找到，不用继续找下去了！
字典树实现
编码函数：
int num(char x){//编码
if(x>='0'&&x<='9')return x-'0';
else if(x>='A'&&x<='Z')return x-'A'+10;
else return x-'a'+36;
}
1.构建字典树
不用建结构体，只需开两个数组，一个变量，分别记录每个点每个字母下一个去的点的编号，该点是否是一个字符串结束的位置，点的编号
int nex[100001][30]={0},cnt=0;
bool b[100001];
我们可以通过存储每个点每个字母下一个要去哪个点，这样就可以实现树上的移动了
如果代码不明白可以回顾一下上文插入方法
void insert(string s){
int p=0;//此点编号
for(int i=0;i<s.size();i++){
int x=num(s[i]);//编码
if(!nex[p][x])nex[p][x]=++cnt;//没有点就新建
p=nex[p][x];//更新所在点
b[p]++;//前缀增加
}
}
调用入口:insert(s);
2.查找
按编号向下查找，如果没有这个点就返回没找到，一直找到最后就可以返回该点是否是一个字符串结束的位置
如果代码不明白可以回顾一下上文查找方法
int find(string s){
int p=0;//此点编号
for(int i=0;i<s.size();i++){
int x=num(s[i]);//编码
if(!nex[p][x])return 0;//没有点就返回0
p=nex[p][x];//更新所在点
}
return b[p];//返回此点末尾是否存在
}
调用入口:find(s);(可以直接cout<<find(s);)
3.结构体封装
int num(char x){//编码(也可以不要)
if(x>='0'&&x<='9')return x-'0';
else if(x>='A'&&x<='Z')return x-'A'+10;
else return x-'a'+36;
}
struct Trie{
int nex[100001][30],cnt=0;
bool b[100001];
void insert(string s){
int p=0;//此点编号
for(int i=0;i<s.size();i++){
int x=num(s[i]);//编码
if(!nex[p][x])nex[p][x]=++cnt;//没有点就新建
p=nex[p][x];//更新所在点
if(i==s.size()-1)b[p]=1;//记录末尾
}
}
int find(string s){
int p=0;//此点编号
for(int i=0;i<s.size();i++){
int x=num(s[i]);//编码
if(!nex[p][x])return 0;//没有点就返回0
p=nex[p][x];//更新所在点
}
return b[p];//返回此点末尾是否存在
}
};
调用入口:t.insert(s);
调用入口:t.find(s);(可以直接cout<<find(s);)
例题1
luogu P8306 【模板】字典树
板子题，只是查找的目的变了而已
点击查看题目
#include<bits/stdc++.h>
using namespace std;
int nex[3000010][70]={0},cnt=0,c[3000010];
int read(){//快读
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
int num(char x){//编码
if(x>='0'&&x<='9')return x-'0';
else if(x>='A'&&x<='Z')return x-'A'+10;
else return x-'a'+36;
}
void insert(string s){
int p=0;//此点编号
for(int i=0;i<s.size();i++){
int x=num(s[i]);//编码
if(!nex[p][x])nex[p][x]=++cnt;//没有点就新建
p=nex[p][x];//更新所在点
c[p]++;//前缀增加
}
}
int find(string s){
int p=0;//此点编号
for(int i=0;i<s.size();i++) {
int x=num(s[i]);//编码
if(!nex[p][x])return 0;//没有点就返回
p=nex[p][x];//更新所在点
}
return c[p];//返回此点前缀
}
int main(){
int T,n,q;
cin>>T;
while(T--){
n=read();
q=read();
for(int i=0;i<=cnt+10;i++)//初始化
for(int j=0;j<70;j++)
nex[i][j]=0;
for(int i=0;i<=cnt+10;i++)c[i]=0;
cnt=0;
for(int i=1;i<=n;i++){//构建字典树
string s;
cin>>s;
insert(s);
}
for(int i=1;i<=q;i++){//查找
string s;
cin>>s;
printf("%d\n",find(s));
}
}
return 0;
}
总结
字典树是一种很有用的数据结构，它在统计，排序和保存大量的字符串方面有很大优势，此外，它还有其他许多功能，在练习中我们可以发现它的更多用处
题单
- luogu P2580 于是他错误的点名开始了 思路:板子题，字符串结束点多一个点名次数标记就行了
- luogu P8306 【模板】字典树 思路:板子题，已讲解
- luogu P4551 最长异或路径 思路:01trie，把数转化为二进制字符串存入trie中，还要贪心一下