各位如果看到博客内有广告,可以动手点一点,谢谢

MENU

TRIE(3)

July 7, 2018 • Read: 347 • 算法

例2 题目链接:hihoCoder1107

image
搜索引擎现在一般都有关键词提示或者说是补全功能。就是当你在搜索框里输入一个关键词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}

image

这时假设我们要查询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

Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment