字典树小结

2020-11-29

字典树小结

最近复习了一下字典树，就顺带总结下字典树的版子，以及常见的使用方法吧

版子

字典树版子

//这种写法过于正式看着让人很不舒服，具体题目时可以自己做简化，怎么简单怎么来


///maxNodes最大节点数，一般是字符串的最大数量乘以字符串的平均长度(或最大长度)
//type字符的总数，一般如果是数字就是10，纯大写或纯小写字母就是26，但是如果涉及到两种及以上就是128，通常会多加一两个放越界
//这里的endWithNode是单词结束的标志，在某些情况下作用很大，尤其是在ac自动机里
const int maxNodes = 100020;
const int type = 12;
int unusedMark, numberOfNodes, root;
int trie[maxNodes][type], endWithNode[maxNodes];

//申请一个新的节点
int newNode() {
    for (int i = 0; i < type; i++)
        trie[numberOfNodes][i] = unusedMark;
    endWithNode[numberOfNodes] = 0;
    return numberOfNodes++;
}

//初始化字典树，并不是memset(trie, -1, sizeof trie)，以为开销太大了，但是如果数组比较小可以直接memset操作，同样是怎么简单怎么来
void Init() {
    unusedMark = -1;
    numberOfNodes = 0;
    root = newNode();
}

//插入字符串，这里就体现了字典树的最大特点，典型的空间换时间
void Insert(char buf[]) {
    int len = strlen(buf);
    int now = root;
    for (int i = 0; i < len; i++) {
        int x = buf[i] - '0';
        if (trie[now][x] == unusedMark) {
            trie[now][x] = newNode();
        }
        now = trie[now][x];
    }
    endWithNode[now]++;
}

int Query(char buf[]) {
    int len = strlen(buf);
    int now = root;
    for (int i = 0; i < len; i++) {
        int x = buf[i] - '0';
        if (trie[now][x] == unusedMark) return 0;
        now = trie[now][x];
    }
    return endWithNode[now];
}

字典树介绍

字典树，顾名思义和字典类似，使用字典查找单词时，当然是先找到第一个字母的范围，然后根据后续的字母依次缩小范围，字典树的插入查询就是这个过程，在插入过程中如果找不到当前字母的后续就给它开辟一个节点来存储
字典树的特点，非常典型的空间换时间，从字典树的版子可以看出，字典树的空间复杂度极高，但是时间复杂度让人很满意

字典树的几个例题

01字典树

一种特殊的字典树，用来处理异或相关的问题，例如找最大异或和

两个数最大异或和

异或：二级制不进位加法，(1,0)/(0,1)异或得1，(1,1)/(0,0)异或得0，异或的两个数相同的值为0，不同则为1
找两个数的最大异或和其实就是找到一个尽可能和一个数和当前数互补，所以我们从高位开始找，尽可能的找与当前位相反的数，在不济也是找到自己

两个数最大异或和 ac代码

#include<bits/stdc++.h>
 
using namespace std;
const int maxNodes = 100000 * 32 + 20;
const int type = 2;
 
int trie[maxNodes][type], totNum;
 
inline void Insert(int n) {
    int now = 0;
    for (int i = 31; ~i; i--) {
        int x = n >> i & 1;
        if (!trie[now][x])  trie[now][x] = ++totNum;
        now = trie[now][x];
    }
}
 
 //这里的ans不是找的互补的数，而是异或之后的结果
 //如果找得到相反的数字，那么这一位异或之后的结果就必然是1，否则就是0
inline int Query(int n) {
    int now = 0, ans = 0;
    for (int i = 31; ~i; i--) {
        int x = n >> i & 1;
        if (trie[now][x ^ 1]) {
            now = trie[now][x ^ 1];
            ans ^= 1 << i;
        }
        else    now = trie[now][x];
    }
    return ans;
}
 
int main () {
    int n, m;
    while (~scanf("%d", &n)) {
        totNum = 0;
        memset(trie, 0, sizeof trie);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", &m);
            Insert(m);
            ans = max(ans, Query(m));
        }
        printf("%d\n", ans);
    }
    return 0;
}

连续最大异或和

这里要用到前缀异或和，由于异或的特点，当两个相同的数字异或时，得到的结果会是0，如果是用前缀异或和sum的话，sum[i - 1] ^ sum[j]就相当于是a[i]连续异或到a[j]，从而优化了时间复杂度，同时将这个问题简化到求两个数的最大异或和问题了
要注意的一点是，这里是i和j是可以相等的，也就是说是可以得到自身的，所以要先插入一个0

连续最大异或和 ac代码

#include<bits/stdc++.h>
 
using namespace std;
const int maxNodes = 400000 * 32 + 20;
const int type = 2;
const int N = 400002;
 
int trie[maxNodes][type], totNum;
int a[N], sum[N], L[N], R[N];
 
inline void Insert(int n) {
    int now = 0;
    for (int i = 30; ~i; i--) {
        int x = n >> i & 1;
        if (!trie[now][x])  trie[now][x] = ++totNum;
        now = trie[now][x];
    }
}
 
inline int Query(int n) {
    int now = 0, ans = 0;
    for (int i = 30; ~i; i--) {
        int x = n >> i & 1;
        if (trie[now][x ^ 1]) {
            now = trie[now][x ^ 1];
            ans ^= 1 << i;
        }
        else {
            now = trie[now][x];
        }
    }
    return ans;
}
 
int main () {
    int n;
    while (~scanf("%d", &n)) {
        totNum = 0;
        memset(trie, 0, sizeof trie);
        for (int i = 1; i <= n; i++)    scanf("%d", &a[i]);
 
        memset(sum, 0, sizeof sum);
        memset(L, 0, sizeof L);
        memset(R, 0, sizeof R);
        Insert(0);
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] ^ a[i];
            Insert(sum[i]);
            L[i] = max(L[i - 1], Query(sum[i]));
        }
        totNum = 0;
        memset(trie, 0, sizeof trie);
        Insert(0);
        for (int i = n; i; i--) {
            sum[i] = sum[i + 1] ^ a[i];
            Insert(sum[i]);
            R[i] = max(R[i + 1], Query(sum[i]));
        }
 
        int ans = 0;
        for (int i = 1; i < n; i++)
            ans = max(L[i] + R[i + 1], ans);
 
        printf("%d\n", ans);
    }
    return 0;
}

普通字典树

L语言

这个题的坑点在于，一个单词可能是另一个单词的前缀

L语言 ac代码

#include<bits/stdc++.h>
using namespace std;
 
const int maxNodes = 2720;
const int type = 27;
int trie[maxNodes][type], endWithNode[maxNodes];
int totNum;
 
void Init() {
    totNum = 0;
    memset(trie, 0, sizeof trie);
    memset(endWithNode, 0, sizeof endWithNode);
}
 
void Insert(char s[]) {
    int now = 0, len = strlen(s);
    for (int i = 0; i < len; i++) {
        int x = s[i] - 'a';
        if (!trie[now][x])  trie[now][x] = ++totNum;
        now = trie[now][x];
    }
    endWithNode[now] = 1;
}
 
int f[1050000];
 
int Query(char s[]) {
    int now = 0, len = strlen(s + 1);
    int ans = 0;
    memset(f, 0, sizeof f);
    f[0] = 1;
    for (int i = 0; i <= len; i++) {
        if (f[i]) {
            now = 0;
            ans = i;
            for (int j = i + 1; j <= len; j++) {
                int x = s[j] - 'a';
                if (trie[now][x])   now = trie[now][x];
                else    break;
                if (endWithNode[now])   f[j] = 1;
            }
        }
    }
    return ans;
}
 
int n, m;
char s[1050000];
 
int main () {
    while (~scanf("%d%d", &n, &m)) {
        Init();
        while (n-- && scanf("%s", s)) {
            Insert(s);
        }
        while (m-- && scanf("%s", s + 1)) {
            printf("%d\n", Query(s));
        }
    }
    return 0;
}