Trie树一般指字典树

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。

典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

3个基本性质：

1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符；

2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；

3. 每个节点的所有子节点包含的字符都不相同。

Trie字符串统计

原题

#include <iostream>
using namespace std;
const int N = 2e4 + 5;
int son[N][26], cnt[N], idx;
char str[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);
    while (n--) {
        char op[2];
        scanf("%s%s", op, str);
        if (op[0] == 'I') {
            insert(str);
        } else {
            printf("%d\n", query(str));
        }
    }
    return 0;
}

#include <iostream>
#include <unordered_set>
using namespace std;
unordered_multiset<string> ms;

int main() {
    int n;
    cin >> n;
    while (n--) {
        char op;
        string str;
        cin >> op >> str;
        if (op == 'I') {
            ms.insert(str);
        } else {
            cout << ms.count(str) << endl;
        }
    }
    return 0;
}

两者的时间差别较大