代码

#include<iostream>
using namespace std;
const int N=100210;
int cnt[N],son[N][26],idx;
char s[N];
void I(char s[])
{
    int p=0;
    for(int i=0;s[i]!=0;i++)
    {
        int u=s[i]-'a';
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]++;
}
int Q(char s[])
{
    int p=0;
    for(int i=0;s[i];i++)
    {
        int u=s[i]-'a';
        if(!son[p][u]) return 0;
        p=son[p][u];
    }
    return cnt[p];
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        char op;
        cin>>op>>s;
        if(op=='I')
        I(s);
        else cout<<Q(s)<<endl;
    }
}

核心

Trie