Trie 树

一、算法思想

Trie 树，又叫 前缀树 或 字典树，是一种用于 快速查询某个字符串 / 字符前缀是否存在 的数据结构。

其核心是使用 边 来代表有无字符，使用 点 来记录是否为单词结尾以及其后续字符串的字符是什么。

二、算法模板

C++

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

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

int query(string s)
{
    int p = 0;
    for (int i = 0; i < s.length(); i++) {
        int t = s[i] - 'a';
        if (!son[p][t]) return 0;
        p = son[p][t];
    }
    return cnt[p];
}

三、代码实战

AcWing 0835

---

题目：Trie 字符串统计

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

1. I x 向集合中插入一个字符串 $x$；
2. Q x 询问一个字符串在集合中出现了多少次。 共有 $N$ 个操作，输入的字符串总长度不超过 $10^5$，字符串仅包含小写英文字母。

输入格式

第一行包含整数 $N$，表示操作数。

接下来 $N$ 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。

输出格式

对于每个询问指令 Q x，都要输出一个整数作为结果，表示 $x$ 在集合中出现的次数。

每个结果占一行。

数据范围

$1 \le N \le 2 \times 10^4$

输入样例：

5

I abc

Q abc

Q ab

I ab

Q ab

输出样例：

1

0

1

解答代码：

#include <iostream>
#include <string>

using namespace std;

const int N = 100010;

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

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

int query(string s)
{
    int p = 0;
    for (int i = 0; i < s.length(); i++) {
        int t = s[i] - 'a';
        if (!son[p][t]) return 0;
        p = son[p][t];
    }
    return cnt[p];
}

int main()
{
    int n;
    scanf("%d", &n);
    
    char op;
    string s;
    for (int i = 0; i < n; i++) {
        cin >> op >> s;
        if (op == 'I') insert(s);
        else printf("%d\n", query(s));
    }
    
    return 0;
}

AcWing 0143

---

题目：最大异或对

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

输入格式

第一行输入一个整数 $N$。

第二行输入 $N$ 个整数 $A_1 \sim A_N$。

输出格式

输出一个整数表示答案。

数据范围

$1 \le N \le 10^5$

$0 \le A_i \lt 2^{31}$

输入样例：

3

1 2 3

输出样例：

3

解答代码：

#include <iostream>

using namespace std;

const int N = 100010, M = 3000000;

int son[M][2], idx;
int a[N];

void insert(int x)
{
    int p = 0;
    for (int i = 30; i >= 0; i--) {
        int t = (x >> i) & 1;
        if (!son[p][t]) son[p][t] = ++idx;
        p = son[p][t];
    }
}

int query(int x)
{
    int ans = 0, p = 0;
    for (int i = 30; i >= 0; i--) {
        int t = (x >> i) & 1;
        
        // 优先找 ~t，使异或值为 1
        if (son[p][!t]) {
            ans += 1 << i;
            p = son[p][!t];
        } else {
            p = son[p][t];
        }
    }
    return ans;
}

int main()
{
    int n;
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        insert(a[i]);
    }
    
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, query(a[i]));
    }
    
    cout << ans << endl;
    
    return 0;
}