算法1

思路：trie树：高效存储和查询字符集合的数据结构，对于存储和查询都需要先遍历，
得到其下标，插入操作，如果当前树没有路，就创建路，怎么理解呢？
相当于我这个u=abc没有出现过,就需要建一条路径，这里++idx,相当于p++，
然后令这一支路位p=son[p][u],cnt[p]++;

查询操作同理，先遍历，得到每个单词的下标，如果找不到，返回0，找到了，返回cnt[p]

get小技巧

    之前在做题的时候，经常会遇到让你输入某种字母,实现某种操作，
比如这里的I，实现插入操作， 像这种情况，最好设置一个op[x]数组，
然后if,,,else去实现函数功能，代码简单逻辑分明

插入模板

void insert(char str[])//这里也可以写成void insert(char *str)
{

    int p=0;
    for(int i=0;str[i];i++)//遍历，是否走到结尾
    {

      int u = str[i] - 'a';//u表示当前节点的编号  
        if(!son[p][u])son[p][u]=++idx;//如果当前树没有路，就创建路
        p=son[p][u];//这是我的新路
    }
    cnt[p]++;//以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];
}

C++ 代码

#include<iostream>

using namespace std;
const int N=100010;
//下标是0的点，既是空节点，又是根节点
int son[N][26],cnt[N],idx;//son每个单词最多可连的子节最多有26个
//cnt表示以当前单词结尾的单纯有多少个，idx存下标
char str[N];
void insert(char str[])
{

    int p=0;
    for(int i=0;str[i];i++)//遍历，是否走到结尾
    {

      int u = str[i] - 'a';//u表示当前节点的编号  
        if(!son[p][u])son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]++;//以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;

}