温故而知新可以为师

tire树的确很简单 一开始学的时候还没怎么懂

现在总算懂了

首先就是一直开节点(p= son[p][u])
son[p][u] = ++idx的作用就是表示建到了哪个点
idx的作用也可以所是用来标记节点的
真的十分牛皮

#include <bits/stdc++.h>
using namespace std;
const int N =1e5+10;
int son[N][26],cnt[N],idx;


void insert1(string ss)
{
    int p = 0;
    for(int i=0;i<ss.size();i++)
    {
        int u=ss[i]-'a';
        if( !son[p][u] )
        son[p][u] = ++idx;
        p=son[p][u];
    }
    cnt[p]++;
}

int query(string ss)
{
    int p=0;
    for(int i=0;i<ss.size();i++)
    {
        int u =ss[i] -'a';
        if(!son[p][u])
            return 0;
        p=son[p][u];
    }
    return cnt[p];
}

int main()
{
    int n;
    cin>>n;

    char a;
    string s;

    while( n -- )
    {
        cin>>a;
        cin>>s;
        if(a=='I')
        {
            insert1(s);
        }
        else
            printf("%d\n",query(s));
    }
    return 0;
}