Trie树

---

主要思想

• 用来快速高效地存储和查找==字符串集合==的数据结构
• 用数组模拟Trie树结构

例题1.Trie字符串统计

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

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

输入格式
第一行包含整数 N，表示操作数。

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

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

每个结果占一行。

数据范围
1≤N≤2∗104

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
                            //idx表示当前用到哪个节点
int son[N][26], cnt[N], idx;//cnt[N]存的是以当前这个点结尾的字符串有多少个
char str[26];               //注意：下标是0的点既是根节点，又是空节点
void insert(char str[]){
    int p = 0;
    for(int i = 0; str[i]; i++){//因为字符串结尾是\0，所以条件这么写
        int u = str[i] - 'a';//把字母映射成数字
        if(!son[p][u]) son[p][u] = ++ idx;//如果这个节点不存在这个字母，就创建出来
        p = son[p][u];//不管存不存在结点，p都是要向前走的，不存在就创建一条路
    }
    
    cnt[p] ++;//以这个点结尾的字符串+1
}

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;//如果不存在就返回0
        p = son[p][u];//如果存在就走过去，因为不是插入，所以不用造路
    }
    return cnt[p];//返回个数
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    
    cin>>n;
    
    while(n--){
        char op[2];
        cin>>op>>str;
        if(op[0] == 'I') insert(str);
        else cout<<query(str)<<endl;
    }
    return 0;
}