例2 题目链接：hihoCoder1107
搜索引擎现在一般都有关键词提示或者说是补全功能。就是当你在搜索框里输入一个关键词s时，搜索引擎会自动提示你一些频率比较高，同时前缀是s的关键词
这道题的大意就是给定你N个高频的查询字符串。然后题目定义如果一个字符串s满足，有不少于5个高频字符串是以s为前缀的，那么我们就称s是“合适的前缀”。同时如果一个“合适的前缀”s，删掉s的最后一个字符之后就不是“合适的前缀”了，那我们就称s是“最短的合适前缀”。最后题目问你对于给定N个高频字符串，一共有几个“最短的合适前缀”
举个例子，假如高频的字符串是如下12个：a ab abc abcde abcde abcba bcd bcde bcbbd bcac bee bbb，那么“最短的合适前缀”一共有4个，是ab bb bc be。需要注意一点是，样例中故意给了两个一样的字符串abcde，提醒你需要处理输入中有重复字符串的情况
首先我们看一下为什么ab是“最短的合适前缀”。以ab为前缀的字符串有ab abc abcde abcde abcba 5个，这里abcde要算2次；而以a为前缀的字符串有6个，多了一个a。所以ab砍掉b之后就不是合适的前缀了，所以ab是一个“最短的合适前缀”
同理以b为前缀的高频字符串有6个，所以b不是合适的；但是bb，bc，be都是合适的，所以bb bc be也都是“最短的合适前缀”
通过对样例的分析，我们可以发现：如果我们用所有高频字符串构造Trie，那么找“最短的合适前缀”其实就是找一个节点p，满足以p为根的子树中的终结点不多于5个，同时以p的父节点为根的子树中的终结点大于5
而关于计算Trie的一个子树中终结点的数目，我们在上一节已经做过这样的题目了。方法是用一个cnt数组（int cnt[MAX_NODE]）在插入字符串的时候把沿途的节点cnt都加一。等所有高频字符串都插入完成之后，遍历trie中的每一个节点，看有几个节点p满足cnt[p]<=5且cnt[p.father]>5
其中遍历trie可以用之前讲的dfs算法，整个算法的伪代码如下：
Insert(W):
P = root
Cnt[p]++
For i = 1...W.len
If p.thru(W[i]) == NULL//没有标识为W[i]的边
P.addChild(W[i],new Node())
P = P.thru(W[i])
Cnt[p]++
P.markEndPoint()//标记P为终结点
DFS(P,father):
If Cnt(p) <= 5 AND Cnt(father) > 5
Ans++
Return
For i = 0...25
If P.thru(i) != 0
DFS(P.thru(i),p)
Main:
For i = 0...N-1
Insert(S[i])
Ans = 0
DFS(root,-1)
Print ANS完整的代码如下：
#include <cstdio>
#include <cstring>
using namespace std;
const int MAX_NODE = 1000000 + 10;
const int CHARSET = 26;
int trie[MAX_NODE][CHARSET] = {0};
int cnt[MAX_NODE] = {0};
int n,ans,k = 1;
char s[2000010];
void insert(char *w) {
int len = strlen(w);
int p = 0;
cnt[0]++;
for(int i = 0;i < len;i++) {
int c = w[i] - 'a';
if(!trie[p][c]) {
trie[p][c] = k;
k++;
}
p = trie[p][c];
cnt[p]++;
}
}
void dfs(int x,int father) {
if(x != 0 && cnt[x] <= 5 && cnt[father] > 5)
ans++;
for(int i = 0;i < 26;i++)
if(trie[x][i])
dfs(trie[x][i],x);
}
int main() {
memset(trie,0,sizeof(trie));
scanf("%d",&n);
for(int i = 0;i < n;i++) {
scanf("%s",s);
insert(s);
}
dfs(0,-1);
printf("%d\n",ans);
return 0;
}第10~23行是插入，基本和上一节带cnt的插入没有区别。稍微有一点不同是，这次我们把cnt[0]也就是根节点也统计进去了。然后就是24~30的DFS，x是当前搜索到的节点编号，father是x的父节点编号。第25行的判断就是如果x不是根，并且x以下的终结点数目不少于5，同时x父节点以下的终结点数目就大于5了。那么x就是“最短的合适前缀”。第27~29行是递归搜索x的子节点。最后main函数里，我们只用调用dfs(0, -1)，dfs过程就会把ans算出来，最后再输出ans就可以了
之前讲的几道题都是和字符串相关的题目，毕竟Trie本身被提出就是来处理字符串问题的数据结构。不过实际上Trie也可以应用在其他的“看上去”不是字符串的场景中。后面我们就讲几道Trie应用在整数xor异或值最大的题目
首先我们看这样一个问题：给定一个包含N个整数的集合S={A1, A2, A3, … AN}。然后有M个询问，每次询问给定一个整数X，让你找一个Ai使得Ai xor X的值最大
这道题我们当然可以用暴力枚举的方法搞定。时间复杂度是O(NM)，伪代码如下：
For i = 1...M
Ans = 0
For j = 1...N
If A[j] xor x > Ans xor x
Ans = A[j]
Print A[j]这道题也是可以用Trie解决的。首先我们知道一个整数可以用二进制表示成一个01串。比如3=(011), 5=(101), 4=(100)……。我们假设输入的整数都在0~2^32-1之间，于是我们可以用一个长度是32位的01串表示一个整数
然后对于给定的N个整数A1, A2, A3, … AN，我们把它们对应的01串都插入到一个trie中。注意这里字符集只有0和1，所以整个trie是一棵二叉树
下面我们举一个例子，为了描述方便，我们假设整数都在0~7之间，也就是可以用3位01串表示。现在假设S={1, 2, 7}，也就是说我们要在Trie中插入{001, 010, 111}
这时假设我们要查询x=4，也就是哪个数和4异或结果最大？4=(100)，我们的做法是在trie树中，尽量与4的二进制位反着走。比如4的第一位（最高位）是1，我们从0出发第一步就尽量沿着0走。因为我们要异或和最大，01相反才能异或值是1。并且这一步是可以贪心的，也就是说如果有相反的边，那么我们一定沿着这条边走。因为最高位异或得1的话，即便后面都是0, 10000…000也要比最高位是0，后面都是1的011111…111大
所以我们第一步沿着标识是0的边，移动到了1号节点；4第二位是0，所以我们沿着标识是1的边移动到4号节点；4的第三位是0，但是4号节点没有标识是1的边，所以我们也只好沿着标识是0的边移动到5号节点。已经到了终结点，所以5号节点对应的A2=(010)2=2就是我们要求的答案，A2 xor 4 = 6是最大的
下面我们不忙写代码，我们先再看一道进阶版的题目：给定一个包含N个整数的数组A=[A1, A2, A3, … AN]，让你求出一段连续的子数组A[l], A[l+1], … A[r]使得异或和A[l] xor A[l+1] xor A[l+2] xor … xor A[r]的值最大
解决这道题目的关键，就是利用之前我们在枚举中提到的一个技巧，就是用前缀和表示部分和。之前我们遇到的部分和题目是加法的和，这里异或的和其实是一样的。我们定义S[i]=A[1] xor A[2] xor A[3] xor … xor A[i]，那么A[l] xor A[l+1] xor A[l+2] xor … xor A[r]就等于S[r] xor S[l-1]。因为两个相同的数异或起来值是0
所以这道题就变成了下面这样：给定一个数组：A=[A1, A2, … AN]，我们先求出对应的xor前缀和S[1], S[2], … S[N]，问题是从S数组中找出两个数使得它们的异或值最大。这时就可以用到上一道题的方法了，伪代码如下：
S = 0
Ans = 0
Trie.insert(0)
For i = 1...N
S = S xor A[i]
T = Trie.search(S)
Ans = max(Ans,T)
Tire.insert(S)
Print(Ans)完整的代码如下：
#include <cstdio>
#include <cstring>
using namespace std;
const int MAX_NODE = 1000000 + 10;
const int CHARSET = 2;
int trie[MAX_NODE][CHARSET] = {0};
int color[MAX_NODE] = {0},a[100000];
int t,n,m,ans,k = 1,b[32];
void insert(int x) {
for(int i = 31;i >= 0;i--) {
b[i] = x % i;
x >>= 1;
}
int p = 0;
for(int i 0;i < 32;i++) {
int c = b[i];
if(!trie[p][c]) {
trie[p][c] = k;
k++;
}
p = trie[p][c];
}
color[p] = 1;
}
int search(int x,int father) {
int ret = 0;
for(int i = 31;i >= 0;i--) {
b[i] = x % i;
x >> =1;
}
int p = 0;
for(int i 0;i < 32;i++) {
int c = 1 - b[i];
if(!trie[p][c]) {
p = trie[p][1 - c];
ret *= 2;
}
else {
p = trie[p][c];
ret = ret * 2 + 1;
}
}
return ret;
}
int main() {
scanf("%d",&t);
while(t--) {
memset(trie,0,sizeof(trie));
memset(color,0,sizeof(color));
insert(0);
ans = 0;
int s = 0;
scanf("%d",&n);
for(int i = 0;i < n;i++) {
scanf("%d",&a[i]);
s = s ^ a[i];
int tmp = search(s);
ans = max(ans,tmp);
insert(s);
}
printf("%d\n",ans);
}
return 0;
}第9~24行是insert函数，这里我们插入一个整数x，先把x对应的二进制01串求出来，b[0]是最高位，b[31]是最低位。然后再把b[0]..b[31]按位插入到trie中
第25~44行是search函数，注意我们要尽量与b[i]反着走，也就是尽量沿着c=1-b[i]走。如果trie[p][c]不存在，那么意味着这一位的异或值只能是0了，即ret = ret * 2；否则以为这一位异或可以是1，即ret = ret * 2 + 1
