Trie

介绍

trie，又称前缀树或字典树，是一种有序树，用来保存关联数组，其中的键通常是字符串。是一种高效的存储和查找字符串的数据结构。

如图所示，如果我想要查找是否有 cat 这个单词，只需要沿着 c -> a -> t 这条路径走。如果路径上有某个结点不存在，则说明不存在这个单词。
另外，如果存在某个单词，我们也需要给这个单词最后的那个结点打上一个标记，表示从根节点走到这个结点的路径是一个单词。

例题

题目描述

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

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

输入样例

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例

1
0
1

代码

#include <iostream>
using namespace std;

const int N = 100010;
int son[N][26], cnt[N], idx;
char str[N];
// son[N]用来存树里的结点 ---> 静态链表
// son[N][26]用来表示结点的键值（26个小写字母）
// cnt[N]用来统计单词出现次数
// idx和静态链表中的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];
    }
                                              // 循环结束后，p就是这个单词的最后一个字母所在结点
    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);
    while (n--) {
        char op;
        scanf(" %c", &op);  
        // 坑：scanf在读入单个字符时不会过滤回车，例如在读入一个'a'之后，输入回车的话，
        // 回车会被存放在缓存区中，下一次scanf会自动把回车读入
        // 解决办法：在%前加一个空格，会告诉scanf忽略前面的空行，而等待第一个非空行元素读入其中。
        if (op == 'I') {
            scanf("%s", str);
            insert(str);
        } else {
            scanf("%s", str);
            printf("%d\n", query(str));
        }
    }
    return 0;
}