当前位置：首页 > news >正文

Trie树专题 [转]

news 来源：原创 2024/4/28 13:24:06

    1、静态建树  速度快，但可能会浪费内存  有的题用动态建树会超时，静态就不超时  
    struct trie  
    {  
        int next[maxnode][size];//小写字母size就是26，十进制就是10，二进制就是2  
        bool end[maxnode];  
        int sz;  
        trie()  
        {  
            memset(next,0,sizeof(next)); //如果值是0，就表示这个节点没有走到过  
            memset(end,false,sizeof(end));  
            sz = 0;  
        }  

        void insert(char s[])  
        {  
            int now = 0;  
            int len = strlen(s);  
            for(int i = 0; i < len; i++)  
            {  
                int index = s[i] - 'a';  
                if ( !next[now][index] ) next[now][index] = ++sz;  
                now = next[now][index];  
            }  
            end[now] = true; //在最后一个字母节点处标记  
        }  

        bool find(char s[])  
        {  
            int now = 0;  
            int len = strlen(s);  
            for(int i = 0; i < len; i++)  
            {  
                int index = s[i] - 'a';  
                if ( !next[now][index] ) return false; // 如果这个节点没有拓展过，也就不存在这个字符串  
                now = next[now][index];  
            }  
            return end[now]; //返回这个节点有没有结束标记  
        }  

    };

    2、动态建树  速度相对慢一些，节约内存  
    struct trie  
    {  
        trie* next[size];  
        bool flag;  
    };  

    void init(trie* x)  
    {  
        x->flag = false;  
        for(int i = 0; i < size; i++) x->next[i] = NULL;  
    }  

    void insert(trie* x,char s[])  
    {  
        int len = strlen(s);  
        for(int i = 0; i < len; i++)  
        {  
            int index = s[i] - 'a';  
            if ( x->next[index] == NULL )  
            {  
                x->next[index] = new trie;  
                init(x->next[index]);  
            }  
            x = x->next[index];  
        }  
        x->flag = true;  
    }  

    bool query(trie* x,char s[])  
    {  
        int len = strlen(s);  
        for(int i = 0; i < len; i++)  
        {  
            int index = s[i] - 'a';  
            if ( x->next[index] == NULL ) return false;  
            x = x->next[index];  
        }  
        return x->flag;  
    }

一、字符串的插入、查找

这是trie树最基础的应用，将字符串从第一个字母开始按顺序在trie树上走一遍，在最后一个字母节点处加一个结束标记。可以去查找一个字符串，也可以解决一个字符串是否为另一个字符串前缀的问题。

题目：HDU 1247

题解：http://blog.csdn.net/chy20142109/article/details/50704122

题目：POJ 2503

题解：http://blog.csdn.net/chy20142109/article/details/50704085

题目：POJ 1056

题解：http://blog.csdn.net/chy20142109/article/details/50704140

题目：POJ 3630

题解：http://blog.csdn.net/chy20142109/article/details/50704174

二、统计每个节点的访问次数

在每一个节点处加一个变量来计数，表示之前加入字符串的时候这个节点到达了多少次，也就是有多少个字符串的前缀是这个字符串。

题目：HDU 1251

题解：http://blog.csdn.net/chy20142109/article/details/50704050

题目：POJ 2001

题解：http://blog.csdn.net/chy20142109/article/details/50704221

三、解决一些带有异或计算的问题

我们可以把整数表示成二进制，把二进制状态的下值插入到字典树中进行操作。

比如：我们想在一个整数的集合中找出一个整数x，使得x和给出的一个数异或结果最大。我们考虑异或运算是按二进制位运算，相异为1，那么我们可以两个数的二进制高位尽可能的相异，就能保证答案是最大的。建trie树的时候从最高位开始往低位走，优先考虑高位，因为高位的权值大，影响大。

还有一些关于异或的小技巧，因为x^x = 0，所以当出现重复的数就会抵消。可以把这个思想运用到一些数据的处理上，现在考虑在一个区间[l,r]内，找出一段连续的数，使其异或后的结果最大/最小。我们用f[i]表示a[1]^a[2]^…^a[i]，那么如果想求一段区间[x,y]的异或值就可以用f[x-1]^f[y]来表示。

回到问题，我们枚举这一段连续的数的结尾，也就是现在有一个f[i],i属于[l,r]，现在想找到一个f[k],k属于[l-1,i-1],使得f[i] xor f[k]结果最大/最小。那么找f[k]的这个过程就可以用f[i]在trie树中去贪心匹配，然后对于每次枚举区间结尾计算出来的最大值更新答案。

题目：HDU 4825

题解：http://blog.csdn.net/chy20142109/article/details/50704023

题目：HDU 5269

题解：http://blog.csdn.net/chy20142109/article/details/50704324

题目：POJ 3764

题解：http://blog.csdn.net/chy20142109/article/details/50704350

题目：CodeForces 282E

题解：http://blog.csdn.net/chy20142109/article/details/50706248