Trie树

高效的存储和查找字符串集合的数据结构；

理解

从根节点开始，判断有没有该类字符，有就向下，没有就添加叶节点，依次存储，把所有结尾点标记一下，然后用Trie高速查找某一个字符出现的次数。
qwerwer
qwe
qerer
ertq
yuyu
先是依次存储qwerwer,然会第二段有qwe就不用添加新的叶节点，第三段因为e不相同，所以要添加一个叶节点用于存储erer,此后的基本类似，有就存储没有就添加；

相关模板

// 插入一个字符串
    void insert(char str[])
    {
        int p = 0;
        for (int i = 0; str[i]; i ++ )
        {
            int u = str[i] - 'a';
            //映射编号：0-25
            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;
            //如果不存在某一个子节点，直接返回0；
            p = son[p][u];
            //有就进行下一个
        }
        return cnt[p];
    }   

模板例子

 [原题链接](https://www.acwing.com/problem/content/837/) 
 #include <iostream>

using namespace std;

const int N = 100010;

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];
         cin>>op>>str;
        if (op[0] == 'I') insert(str);
        else cout<<query(str)<<endl;
    }
    return 0;
}