TRIE（3）

例 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