Trie学习总结
hyfhaha
2019-04-10 17:27:55
# [更好的阅读体验](https://www.cnblogs.com/hyfhaha/p/10684418.html)
# Trie树学习总结
字典树，又称前缀树，是用于快速处理字符串的问题，能做到快速查找到一些字符串上的信息。
另外，Trie树在实现高效的同时，会损耗更多的空间，所以Trie是一种以空间换时间的算法。
# Trie的思想
Trie的思想十分简单，其实我在很早之前就已经懂了Trie的思想，只不过一直没有实现，所以就……
咕咕，没事，Trie无论是思想还是代码思想都还是很简单。现在我重新再搞回Trie也很快就代码实现了。
Trie是思想其实用图更容易展现。下面放一张图给大家看看，相信大家很快就会明白了。
如果我们插入字符串：
```
zlh
AK
tql
AKIOI
AKnoip
```
上面就是一颗我们建的Trie树。
如果我们要查找“zlh”，那么就会沿着1->2->3点找下去。
如果我们要查找“AKIOI”，那么我们就会沿着4->5->9->10->11点找
也可以十分容易发现"AK"是"AKIOI"的前缀。
那么大家现在应该就能明白Trie的构造了吧。
简单说就是顺着之前Trie树的构造去插入点，例如我们最后插入"AKnoip"，就会先走过"A"和"K"，然后发现没有匹配的字符了，就先后新建了'n','o','i','p'，这几个点。复杂度O(len(字符串))。
查询就会沿着Trie的构造一个一个跳，所以查询复杂度是O(len(字符串))。
那么Trie的思想就是这样了。
# Trie的实现
明白了思想，实现就应该很简单了吧，这里通过一道例题来实现Trie。
题目：[P2580 于是他错误的点名开始了](https://www.luogu.org/problemnew/show/P2580)
### 定义
```cpp
struct kkk{
int son[27],cnt;
bool flag;
}trie[maxn];
```
### 首先是插入操作：
```cpp
void insert(string s){
int len=s.size(),u=0; //获取长度len，u是当前点的编号，根的编号是0
for(int i=0;i<len;i++){
int v=s[i]-'a'; //获取位置
if(!trie[u].son[v]) //如果没有继续下去的节点
trie[u].son[v]=++num; //就新建一个
u=trie[u].son[v]; //跳到下一个点去插入
}
trie[u].flag=true; //标记此处是一个单词
}
```
### 然后是查询操作：
```cpp
int find(string s){
int len=s.size(),u=0;
for(int i=0;i<len;i++){
int v=s[i]-'a'; //同上
if(!trie[u].son[v])return 3; //找不到返回没有
u=trie[u].son[v]; //同上
}
if(trie[u].flag==false)return 3; //不是一个单词就返回没有
if(!trie[u].cnt){ //如果没有被点过
trie[u].cnt++; //标记被点过了
return 1; //返回有
} return 2; //不然返回重复
}
```
那么Trie的实现就这样了。
## Trie的考点
1. 异或XOR以及利用XOR的性质
2. 后缀转前缀
3. 记忆化，缩点，重构树，Trie的思想（见 P3294 [SCOI2016]背单词，P2292 [HNOI2004]L语言
4. 可持久化（详见下文
# 随便给点题
phone list
The XOR Largest Pair
Nikitosh 和异或
Immediate Decodability
[SCOI2016]背单词
[HNOI2004]L语言
[USACO08DEC]秘密消息Secret Message
最长异或路径
#### 做完上面那几道应该就能了解**Trie**了
# 习题讲解
## 1、phone list
题目：[Phone list](https://www.luogu.org/problemnew/show/UVA11362)
题目意思十分明确，求有没有一个字符串是其他字符串的前缀，如果有就返回"NO"，没有返回"YES"。
这题和前面讲的Trie的作用一模一样，可以快速判断一个字符串是不是已插入的字符串中的前缀。
那么这道题就很简单了，我们先将全部字符串都插入到Trie中。
然后查找每一个字符串，如果字符串下有儿子，那么就代表当前字符串是某个字符串的前缀，直接返回。
代码实现也很简单，可以算是Trie的模板题。
```cpp
#include<bits/stdc++.h>
using namespace std;
struct kkk{
int son[11],sum;
bool flag;
void clear(){memset(son,0,sizeof(son));sum=0;flag=0;} //清0
}trie[400001];
int n,T,num;
string S[400001];
void insert(string s){
int len=s.size(),u=0;
for(int i=0;i<len;i++){
int v=s[i]-'0';
if(!trie[u].son[v])
trie[u].son[v]=++num;
trie[u].sum++; //表示u有多少个儿子
u=trie[u].son[v];
}
trie[u].flag=true;
}
int find(string s){
int len=s.size(),u=0;
for(int i=0;i<len;i++){
int v=s[i]-'0';
if(!trie[u].son[v])return 0; //找不到字符串就返回
u=trie[u].son[v];
}
if(trie[u].sum==0)return 0; //如果没有儿子就代表不是前缀
return 1; //否则就是前缀
}
int main(){
scanf("%d",&T);
while(T--){
num=0; //记得清0
for(int i=0;i<=400000;i++)trie[i].clear(); //记得清0
scanf("%d",&n);
for(int i=1;i<=n;i++){
cin>>S[i];
insert(S[i]); //一个一个插入
}
bool ans=false;
for(int i=1;i<=n;i++){
int res=find(S[i]); //查询
if(res==1){ans=true;break;} //判断是不是前缀
}
if(ans==true)printf("NO\n"); //输出
else printf("YES\n");
}
}
```
## 2、Immediate Decodability
题目：[Immediate Decodability](https://www.luogu.org/problemnew/show/UVA644)
这道题和上面那道题一模一样，不过输入比较恶心，而且数据范围也比较小。
这里的输入就是不断输入字符串S，然后将字符串S插入到Trie中，直到S='9'为止。
到了S='9'，就将之前的S都像上面的一样查询一边，输出答案，然后清0。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
struct kkk{
int son[11],sum;
bool flag;
void clear(){memset(son,0,sizeof(son));sum=0;flag=0;}
}trie[2001];
int n,T,num,t;
string S[400001];
void insert(string s){
int len=s.size(),u=0;
for(int i=0;i<len;i++){
int v=s[i]-'0';
if(!trie[u].son[v])
trie[u].son[v]=++num;
trie[u].sum++;
u=trie[u].son[v];
}
trie[u].flag=true;
}
int find(string s){
int len=s.size(),u=0;
for(int i=0;i<len;i++){
int v=s[i]-'0';
if(!trie[u].son[v])return 0;
u=trie[u].son[v];
}
if(trie[u].sum==0)return 0;
return 1;
}
void solve(){ //解决之前的字符串
bool ans=false;
for(int i=1;i<=n;i++){
int res=find(S[i]);
if(res==1){ans=true;break;}
}
if(ans==true)printf("Set %d is not immediately decodable\n",t);
else printf("Set %d is immediately decodable\n",t);
}
int main(){n=1;
while(cin>>S[n]){
if(S[n]=="9"){
t++;
solve(); //解决之前的问题
memset(trie,0,sizeof(trie)); //清0
num=0;n=1;continue; //清0
}
insert(S[n]);n++; //如果不是‘9’就插入
}
}
```
## 3、The XOR Largest Pair
题目：[The XOR Largest Pair](https://loj.ac/problem/10050)
这道题是一道变向的Trie，也是Trie的一个基本应用。
思路：
1、首先将a[i]转换为二进制的字符串存起来，记得空位要补0
2、然后将这些字符串都插入到Trie里。
3、查询每一个字符串，找到以每一个数和另外其他数的最大异或和。
那么问题就是怎么找一个数和另外其他数的最大异或和了。
我们知道，异或是不同就为1，相同就为0，所以我们因尽量让高位的二进制为1。
所以我们查询的时候就倒着查，也就是如果s[i]为0，那么我们就查1。但是没有1怎么办，我们总不能就此放弃吧，于是我们继续查0。
最后取个最大值就OK了。
看看代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
struct kkk{
int son[3],sum;
bool flag;
void clear(){memset(son,0,sizeof(son));sum=0;flag=0;}
}trie[4000001];
int n,T,num,ans;
int x[1000001];
void insert(string s){ //插入
int len=s.size(),u=0;
for(int i=0;i<len;i++){
int v=s[i]-'0';
if(!trie[u].son[v])
trie[u].son[v]=++num;
trie[u].sum++;
u=trie[u].son[v];
}
trie[u].flag=true;
}
int find(string s){
int len=s.size(),u=0,ans=0,num=(int)(2147483648ll/2ll);
for(int i=0;i<len;i++){
int v=((s[i]-'0')^1); //倒着查
if(!trie[u].son[v])v^=1; //找不到就倒回来
else ans+=num; //不然就累加进去
u=trie[u].son[v];num/=2; //跳下一个
}
return ans;
}
string decompose(int x){ //拆分成二进制
string s="";
while(x!=0)
s+=(x%2)+'0',x>>=1;
while(s.size()!=31)s+='0';
reverse(s.begin(),s.end());
return s; //返回字符串
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&x[i]);
string s=decompose(x[i]);
insert(s);
}
for(int i=1;i<=n;i++){
int res=find(decompose(x[i]));
ans=max(ans,res); //取最大值
}
printf("%d\n",ans);
}
```
## 4、[USACO08DEC]秘密消息Secret Message
题目大意：给你n个信息和m个密码，要你求出对于每一个密码都多少信息，使这些信息的前缀和密码的前缀相同。
理解清题目，这道题就很简单了，我们用信息来在建立Trie时多维护一个数据sum，存的是有多少个信息经过这个节点。那么我们在查询时，先统计有多少信息是密码的前缀再加上当前节点的sum就是答案。
```cpp
#include<bits/stdc++.h>
using namespace std;
struct kkk{
int son[11],sum,flag;
void clear(){memset(son,0,sizeof(son));sum=0;flag=0;}
}trie[400001];
int n,T,num,ans;
string S[400001];
void insert(string s){
int len=s.size(),u=0;
for(int i=0;i<len;i++){
int v=s[i]-'0';
if(!trie[u].son[v])
trie[u].son[v]=++num;
u=trie[u].son[v];trie[u].sum++; //记录sum
}
trie[u].flag++; //有重复所以要加加
}
int find(string s){
int len=s.size(),u=0,ans=0;
for(int i=0;i<len;i++){
int v=s[i]-'0';
if(!trie[u].son[v])return ans; //找不到
u=trie[u].son[v];
ans+=trie[u].flag; //记录信息是密码前缀
}
return ans-trie[u].flag+trie[u].sum; //-trie[u].flag是为了去重
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);string s="";char c;
for(int j=1;j<=x;j++)cin>>c,s+=c;
insert(s);
}
for(int i=1;i<=m;i++){
int x;
scanf("%d",&x);string s="";char c;
for(int j=1;j<=x;j++)cin>>c,s+=c;
ans=find(s);
printf("%d\n",ans);
}
}
```
## 5、Nikitosh 和异或
题目在这里：[「一本通 2.3 例 3」Nikitosh 和异或](https://loj.ac/problem/10051)
首先对于如何求异或最大值我们已经在上文学到了，现在我们要求的是两个没有覆盖的区间异或的和。
异或有一个**性质**：就是据有可减性，也就是说我们记前缀异或sum数组，如果求[l,r]的异或和，那么答案就是sum[r]^sum[l-1];后缀异或也是一样的
所以我们可以对于每一个位置i都求一遍以i为结尾的区间中，最大的区间异或值。方法是将i前面的每一个前缀sum数组都插入到Trie中，然后find(sum[i])，答案计为**l数组**。
另外，对于每一个位置i都求一遍以i为开头的区间中，最大的区间异或值。方法是将i后面的每一个后缀sum数组都插入到Trie中，然后find(sum[i])，答案计为**r数组**。
那么对于每一个位置i，都统计前面的最大的l，记录下来。表示的是i前面的最大区间异或和
对于每一个位置i，都统计后面的最大的r，记录下来。表示的是i后面的最大区间异或和
那么答案就是对于每一个位置i的 前面的最大区间异或和 和 后面的最大区间异或和 的 和 的最大值
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
struct kkk{
int son[3];
void clear(){memset(son,0,sizeof(son));}
}trie[8000001];
int n,T,num,ans;
int x[1000001],l[1000001],r[1000001],s[35];
void insert(int x){
int j=-1,u=0;
memset(s,0,sizeof(s));
while(x){
s[++j]=x&1;
x>>=1;
}
for(int i=31;i>=0;i--){
if(!trie[u].son[s[i]])
trie[u].son[s[i]]=++num;
u=trie[u].son[s[i]];
}
}
int find(int x){
int ans=0,u=0;
for(int i=31;i>=0;i--){
int v=1-s[i];
if(!trie[u].son[v])v^=1;
else ans+=(1<<i);
u=trie[u].son[v];
}
return ans;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&x[i]);
}
int sumx=0;num=0;
for(int i=1;i<=n;i++)
sumx^=x[i],insert(sumx),
l[i]=max(l[i-1],find(sumx));
memset(trie,0,num+1);
sumx=0;num=0;
for(int i=n;i>=1;i--)
sumx^=x[i],
insert(sumx),
r[i]=max(r[i+1],find(sumx));
for(int i=1;i<n;i++)ans=max(ans,l[i]+r[i+1]);
printf("%d\n",ans);
}
```
# 可持久化Trie