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*10^4$

输入样例：

1
2
3
4
5
6
5
I abc
Q abc
Q ab
I ab
Q ab

输出样例：

1
2
3
1
0
1

题目分析

只要根据题目的输入建立trie树即可，维护两个操作，一个是insert插入字符串的操作，一个是query查询字符串数量的操作，需要注意的是代码中的idx表示节点的编号，每次当某一位置的字符串之前没出现过时，idx会自增1，题目中总字符数量不会超过$10^5$，idx为零的点，既是根节点，又是空节点指向的点。可以将这个trie树理解成一个个的单链表，idx为0表示到达链表末尾。

举个具体的例子：

比如先后插入字符串abcdef、abdef、aced之后的son数组（蓝色数字表示是字符串末尾）：

a b c d e f g
0 1
1 2 10
2 3 7
3 4
4 5
5 6
6
7 8
8 9
9
10 11
11 12
12

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;

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

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], str[N];
    while(n --) {
        scanf("%s%s", op, str);
        if(*op == 'I') insert(str);
        else printf("%d\n", query(str));
    }
    return 0;
}

相关模板题

最大异或对

在给定的 𝑁 个整数 $𝐴1，𝐴_2……𝐴𝑁$ 中选出两个进行𝑥𝑜𝑟（异或）运算，得到的结果最大是多少？

输入格式

第一行输入一个整数 𝑁。

第二行输入 𝑁 个整数 $𝐴1～𝐴𝑁$。

输出格式

输出一个整数表示答案。

数据范围

$1 \le 𝑁 \le 10^5,$
$0 \le 𝐴𝑖 < 2^{31}$

输入样例：

1
2
3
1 2 3

输出样例：

1
3

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 3100010;
int nums[N], n, son[M][2], idx;


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

int query(int a) {
    int p = 0;
    int res = 0;
    for(int i = 30; ~i; i --) {
        int u = a >> i & 1;
        if(son[p][!u]) {
            res += 1 << i;
            p = son[p][!u];
        }
        else {
            p = son[p][u];   
        }
    }
    return res;
}

int main(){
    scanf("%d", &n);
    for(int i = 0 ;i < n; i ++) {
        scanf("%d", &nums[i]);
        insert(nums[i]);
    }
    int res = 0;
    for(int i = 0; i < n; i ++) res = max(res, query(nums[i]));
    printf("%d", res);
    return 0;
}