关于Trie树（字典树/前缀树）

总结了使用Trie树（字典树/前缀树）解决的一些问题，包括字符串前缀相关（Trie字符串统计、前缀统计）和异或运算相关（最大异或对、最大异或和）等问题。

字符串前缀相关

Trie字符串统计

• 问题描述

如Trie字符串统计所描述：

维护一个字符串集合，支持两种操作：

1. I x 向集合中插入一个字符串$x$；
2. Q x 询问一个字符串在集合中出现了多少次。

共有$N$个操作，所有输入的字符串总长度不超过$10^5$，字符串仅包含小写英文字母。

…

• 问题分析

使用Trie树可以高效地保存和查找字符串。

• 代码实现

#include <iostream>
using namespace std;

const int N = 100010;

int son[N][26], cnt[N], idx;

// 插入操作
void insert(char str[]) {
    int p = 0;
    for (int i = 0; str[i]; i ++) {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++;
}

// 查询操作
int query(char str[]) {
    int p = 0;
    for (int i = 0; str[i]; i ++) {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

int main() {
    int n;
    scanf("%d", &n);
    char op[2], tmp[N];
    while (n --) {
        scanf("%s", op);
        scanf("%s", tmp);
        if (op[0] == 'I') {
            insert(tmp);
        }
        else {
            printf("%d\n", query(tmp));
        }
    }
    return 0;
}

前缀统计

• 问题描述

如前缀统计所描述：

给定$N$个字符串 $S_1,S_2…S_N$，接下来进行$M$次询问，每次询问给定一个字符串$T$，求 $S_1∼S_N$中有多少个字符串是$T$的前缀。

输入字符串的总长度不超过$10^6$，仅包含小写字母。

…

• 问题分析

使用Trie树可以快速地查找字符串前缀。

• 代码实现

#include <iostream>
using namespace std;

const int N = 1000010;
int son[N][26], cnt[N], idx;

void insert(string &str) {
    int p = 0;
    for (int i = 0; i < str.size(); i ++) {
        int &s = son[p][str[i] - 'a'];
        if (!s) s = ++ idx;
        p = s;
    }
    cnt[p] ++;
}

int query(string &str) {
    int res = 0, p = 0;
    for (int i = 0; i < str.size(); i ++) {
        int u = str[i] - 'a';
        if (!son[p][u]) break;
        p = son[p][u];
        res += cnt[p];		// 注意要在 son[p][u] 赋值给 p 之后统计数量，否则统计的是以前一个字符结尾的数量
    }
    return res;
}

int main() {
    int n, m;
    cin >> n >> m;
    string str;
    while (n --) {
        cin >> str;
        insert(str);
    }
    
    while (m --) {
        cin >> str;
        cout << query(str) << endl;
    }
    
    return 0;
}

• 问题描述

如单词替换所描述：

在英语中，我们有一个叫做 词根(root) 的概念，可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。

现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。

你需要输出替换之后的句子。

…

• 问题分析

使用Trie树可以高效地查找字符串前缀。

• 代码实现

class Solution {
public:
    // 注意，面试中应以结构体形式书写
    struct Node {
        int cnt;
        Node *son[26];
        Node() {
            cnt = 0;
            // 注意此处的 & 符号，若忽略了些符号，则初始化失败，son数组中储存的是野指针
            for (Node* &s : son) s = nullptr;
        }
    } *root;
    string replaceWords(vector<string>& dictionary, string sentence) {
        root = new Node();
        int n = sentence.size();
        for (string word : dictionary) {
            insert(word);
        }
        string res = "";
        int i = 0, j = 0;
        // 对单词进行分割
        while (i < n) {
            while (i < n && sentence[i] != ' ') i ++;
            string sub = sentence.substr(j, i - j);
            res += query(sub);
            if (i < n) {
                i = i + 1, j = i;
                res += " ";
            }
            else return res;
        }
        return res;
    }

    void insert(string &word) {
        Node *p = root;
        for (int i = 0; i < word.size(); i ++) {
            int u = word[i] - 'a';
            if (!p->son[u]) p->son[u] = new Node();
            p = p->son[u];
        }
        p->cnt ++;
    }

    string query(string &word) {
        string res;
        Node *p = root;
        for (int i = 0; i < word.size(); i ++) {
            int u = word[i] - 'a';
            if (!p->son[u]) return word;
            p = p->son[u];
            if (p->cnt) return word.substr(0, i + 1);
        }
        // 若字典中的单词比句子中的单词更长（即句子中的单词是字典中单词的前缀），则直接返回句子中的单词。
        return word;
    }
};

异或运算相关

最大异或对

• 问题描述

如最大异或对所描述：

在给定的$N$个整数$A_1，A_2……A_N$ 中选出两个进行 $xor$（异或）运算，得到的结果最大是多少？

…

• 问题分析

要使异或运算最大，则需要查找对于输入的某一个整数$A_i$，是否存在整数$A_j$，使得整数$A_j$从高位到低位在每一位都尽量与$A_i$相反。考虑使用Trie树输入的整数进行存储，并从高到低位进行查找。

• 代码实现

#include <iostream>
using namespace std;

const int M = 3100010; // 因为最多有 100000 个整数，而每个整数最多 31 位，故最多 M 节点
int son[M][2], idx;

void insert(int x) {
    int p = 0;
    // 一定要注意要从高位到低位进行存储和查找，否则找到的可能不是最大值
    for (int i = 30; ~i; i --) {
        int u = x >> i & 1;
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
}

int check(int x) {
    int p = 0, tmp = 0;
    for (int i = 30; ~i; i --) {
        int u = x >> i & 1;
        if (son[p][!u]) {
            tmp += 1 << i;
            p = son[p][!u];
        }
        else p = son[p][u];
    }
    return tmp;
}

int main() {
    int n;
    cin >> n;
    int tmp, res = 0;
    for (int i = 0; i < n; i ++) {
        cin >> tmp;
        insert(tmp);
        res = max(res, check(tmp));
    }
    cout << res << endl;
    return 0;
}

最大异或和

• 问题描述

如最大异或和所描述：

给定一个非负整数数列$a$，初始长度为$N$。

请在所有长度不超过$M$的连续子数组中，找出子数组异或和的最大值。

子数组的异或和即为子数组中所有元素按位异或得到的结果。

注意：子数组可以为空。

…

• 问题分析

1. 注意到异或运算的性质：

   • 恒等律：$a \oplus 0=a$
   • 归零律：$a\oplus a=0$
   • 交换律：$a\oplus b=b\oplus a$

   同时，由题干中的“连续子数组”，可以联想到使用前缀和来解决。结合异或运算的性质，可以得到：

   $$S_{L-1} = a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_{L-1}\\ S_R = a_1 \oplus a_2 \oplus a_3 \oplus ... \oplus a_R\\ S_R \oplus S_{L-1}= a_1 \oplus a_1 \oplus a_2 \oplus a_2 ... \oplus a_{L-1} \oplus a_{L-1} \oplus a_{L} \oplus a_{L+1} ... \oplus a_R=a_L \oplus a_{L+1} ... \oplus a_R$$

   因此可以将问题转换为前缀异或数组中两个数之间的异或和的最大值。

2. 根据题干，子数组有最大长度限制，因此前缀树需要有删除操作，当插入前缀树的数组长度大于$M$时，删除多余的数。

• 代码实现

#include <iostream>
using namespace std;

const int N = 100010, M = 3100010;
int s[N], son[M][2], idx, cnt[M];

// x：插入的元素的值
// s：若为 1 则为插入元素，若为 -1，则为删除元素
void insert(int x, int s) {
    int p = 0;
    for (int i = 30; i >= 0; i --) {
        int u = x >> i & 1;
        // 使用 cnt 数组存储当前节点对应的集合的元素个数，每删除一个数，对应的值减 1
        if (!cnt[son[p][u]]) son[p][u] = ++ idx;
        p = son[p][u];
        cnt[p] += s;
    }
}

int query(int x) {
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i --) {
        int u = x >> i & 1;
        if (cnt[son[p][!u]]) p = son[p][!u], res = res * 2 + 1;
        else p = son[p][u], res *= 2;
    }
    return res;
}

int main() {
    int n, m;
    cin >> n >> m;
    int t;
    for (int i = 1; i <= n; i ++) {
        cin >> t;
        s[i] = s[i - 1] ^ t;
    }
    
    int res = 0;
    insert(s[0], 1); // 注意要先把前缀和第一个元素 s[0] 插入
    for (int i = 1; i <= n; i ++) {
        if (i - m - 1 >= 0) insert(s[i - m - 1], -1); // 超过最大数据长度 M，删除元素
        res = max(res, query(s[i]));
        insert(s[i], 1);
    }
    cout << res << endl;
    return 0;
}