Trie字符串统计

题目描述

维护一个字符串集合，支持两种操作：
    I x 向集合中插入一个字符串 x；
    Q x 询问一个字符串在集合中出现了多少次。
共有 N
个操作，所有输入的字符串总长度不超过 105
，字符串仅包含小写英文字母。
输入格式
第一行包含整数 N
，表示操作数。
接下来 N
行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。
输出格式
对于每个询问指令 Q x，都要输出一个整数作为结果，表示 x
在集合中出现的次数。
每个结果占一行。
数据范围
1≤N≤2∗104
输入样例：
5
I abc
Q abc
Q ab
I ab
Q ab
输出样例：
1
0
1

通过题目描述可以得知，我们需要维护一个数据结构，来完成我们的记录操作。
第一眼看到题时，看起来很简单，但实际上还得使用到一个数据结构 : Trie树
Trie树就是

Trie 树，又称字典树，是用来 高效存储和查找字符串集合 的一种数据结构查找时，可以 高效的查找某个字符串 是否 在Trie 树中出现过，并且可以查找出现了多少次
利用字符串的 公共前缀 来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。 

了解了Trie树之后，我们来实现Trie树。
这里使用的是二维数组

int son[100005][26];

定义之后，我们还要一个记录用的数组

int cnt[100005];

这两个就是程序的关键
我们可以把Trie树看成这种形式

知道这些之后，就可写代码了

代码

#include <bits/stdc++.h>
using namespace std;
int n;
int son[100005][26], cnt[100005], idx;

void insert(string 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(string 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(){
    cin >> n;
    while(n --){
        char op;
        cin >> op;
        if(op == 'I'){
            string s;
            cin >> s;
            insert(s);
        }else{
            string s;
            cin >> s;
            cout << query(s) << endl;
        }
    }
    return 0;
}