Trie树（字典树）可以高效地存储和查询字符串！

C++ 代码

#include<iostream>
#include<algorithm>

using namespace std;
const int N=1e5+10;

int son[N][26];//Trie树。 高效的存储和查询字符串
int cnt[N];//标记每个字符串出现的次数
int index;
char str[N];
//插入字符串
void insert(char str[])
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';//把 a~z 映射到 0~25
        if(!son[p][u])son[p][u] = ++index; //如果没有当前儿子，创建
        p=son[p][u];//有当前儿子，p更新
        //son 既指示位置，也指示有没有
    }
    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;
    cin>>n;
    while(n--){
        char op;
        cin>>op>>str;
        if(op=='I')insert(str);
        else cout<<query(str)<<"\n";
    }
    return 0;
}