Trie教程

dg-publish: "true"
dg-home: "true"

字典树是一种用于实现字符串快速检索的多叉树结构。

可以用二维数组构造字典树，对字符串中的字符按顺序编号，每个结点有26个孩子（假设只有英文字母）。
初始化
一棵空$Trie$(字典树)仅包含一个根节点，该节点的字符串指针（孩子节点位置）均指向空。
插入
当需要插入一个字符串$S$时，让一个指针$P$指向根节点。然后，依次扫毛$S$中的每个字符$c$。
1.若$P$的孩子节点$c$已有值，例如值为$Q$，则移动指针$P$到位置$Q$。
2.若$P$的$c$字符孩子节点为空，则新建一个节点$Q$(数组模拟，新增节点，只需原长度基础上增加一个位置），让$P$的$c$字符孩子节点保存新节点的下标$Q$。然后移动$P$到为止$Q$。
当$S$中的字符扫描结束时，在当前节点$P$上标记它是一个字符串的末尾。
检索
当需要检查一个字符串$S$在$Trie$中是否存在时，我们令$P$指向根节点，然后依次扫描$S$中的每个字符$c$。
1.若$P$中的$c$字符孩子节点不存在，说明这个字符串没出现过，结束搜索。
2.若$P$中的孩子节点$c$有值，移动$P$至孩子节点。
当$S$扫描结束时，若当前$P$表示的位置被标记为字符串的结尾，说明字符串存在，反之不存在。
1.全局变量

int trie[SIZE][26],tot=1;  //tot节点编号 初值1，表示根节点
bool end[SIZE]; //记录节点编号是否是单词末尾节点

2.字典树构造

void ins(string &s)
{
	int p = 1;
	for(int i = 0; i < s.size(); i++){ //枚举单词
		int x = s[i]-'a'; 
		if(trie[p][x]==0) trie[p][x]=++tot; //节点编号
		p=trie[p][x]; //p指向下一个字符的节点
	}
	end[p]=true; //最后节点编号记为单词末尾节点 
}

3.字典树查询

bool search(string &s)
{
	int p = 1,sum = 0;
	for(int i = 0; i < s.size(); i++){
		p = trie[p][s[i]-'a']; //取出字符所在节点编号
		if(p == 0) return false; //编号为0，说明没有这个单词
	}
	return end[p];  //最后一个字符是否是单词末尾
}

例题提示

7133: 【S】前缀统计
题目要求前缀字符串出现的次数。
所以在字典树构造的时候，原用于标记单词结尾的$end$数组，改为计数数组，例如$cnt$。那么最后的$end[p]=true$改为计数次数$cnt[p]++$。
那么在查询的时候，每扫描一个字符，只要$cnt$不为$0$（意味着前缀），就需要累加起来。
1827: 单词查找树
要计算节点个数，那不就是$tot$吗？
7134: 【S】The XOR Largest Pair
字符串扫描，改为二进制位扫描，注意下标$0$是低位，所以扫描要从下标$31$开始（题目没说一定是正数）。

...
for(int i = 31; i >= 0; i--){
    int m = (x>>i)&1;
    if....
}
...

因为是异或，所以查询应该取反搜素，即当前0，去搜1；当前1，则去搜0。

...
for(int i = 31; i >= 0; i--){
    int m = (x>>i)&1;
    if(trie[p][m^1]){
        s+=(1<<i); //移回去，异或结果为1
        p=trie[p][m^1];
    }else p=trie[p][m]; //如找不到，则沿原路继续前进
}
...

因为题目要求序列中两个正整数异或的最大值，所以需要枚举序列，这里注意，已经构建了字典树，只要枚举一个数就可以了，另一个在查询的时候就在寻找了。
7230: 「一本通 2.3 例 1」Phone List
要判断在给出的数据中，是否存在$S$是$T$的前缀。
那么首先构建字典树，然后枚举字符串，搜索字符串是否存在当前字符串的前缀。
其实只要在搜索的时候，如果节点存在，加一个判断即可。

 if(ed[p] && i < s.size() - 1) return 1;

7232: 「一本通 2.3 练习 1」Immediate Decodability
做法跟7230: 「一本通 2.3 例 1」Phone List类似。
2437: 【USACO-2008-DEC-金组】秘密信息
这题并不是求一个是另一个的前缀，而是其他信息是当前信息的前缀或当前信息是其他信息的前缀，可以看成前缀统计的升级版。
所以，不能只在字符串结束的时候进行统计，中间构造字典树的时候也要统计。
具体如何计算呢？分两种情况：
1.其他信息是当前信息的前缀。
2.当前信息可能完全属于另一条信息的前缀。
所以，需要两个计数数组：用于统计单词个数的cnt数组，用于统计经过节点次数的$dp$数组，也可以看成动归来理解，所以取名为$dp$。
那么在构造字典树的时候，每扫描一个字符，对应字符节点次数加1，即$dp[p]++$，理解成经过的单词数。
当字符串扫描结束的时候，单词数$cnt[p]++$。
查询也需要修改：当扫描字符的时候，先统计其他信息是当前信息的前缀，也就是当前节点存在数据的情况下：

...
if(当前数字节点不存在) return sum; //返回之前统计的前缀数量
sum=sum+cnt[p]; //存在,字典树种的信息是当前信息的前缀
...

如何计算当前信息是其他信息的前缀呢？
在扫描结束后，累加$dp[p]$，表示经过节点$p$的信息数量。

sum=sum+dp[p];

但是，如果节点$p$存在单词（信息），之前搜的过程中已经统计进去，所以此时还要去掉重复的$cnt[p]$后，剩下次数的就是查询的信息是字典树中信息的前缀：

if(cnt[p]) sum -= cnt[p];

查询部分代码：

int check(int x){
    int p=1,sum=0,tag = 0;
    for(int i = 1; i <= x; i++){
        if(trie[p][a[i]]==0) return sum;
        p=trie[p][a[i]];
        sum+=cnt[p];        
    }
    sum+=d[p]; //加上经过p的信息数量
    sum-=cnt[p]; //如果存在，去重；如果不存在，cnt[p]为0
    return ans;
}