静态数组
用数组存储
#include <iostream>
using namespace std;
const int N=100010;
int son[N][26],cnt[N],pos=0;
//每个结点的子节点最多26
void insert(char str[])
{
int p=0;//从根开始
for(int i=0;str[i];i++)//插入字符串str
{
int k=str[i]-'a';
if(son[p][k]==0) son[p][k]=++pos;
p=son[p][k];
}
cnt[p]++;
}
int query(char str[])
{
int p=0;
for(int i=0;str[i];i++)
{
int c=str[i]-'a';
if(son[p][c]==0) return 0;
p=son[p][c];
}
return cnt[p];
}
int main()
{
int n;
cin>>n;
char str[N];
for(int i=0;i<n;i++)
{
char op;
cin>>op;
getchar();
cin.getline(str,N);
if(op=='I')
{
insert(str);
}
else if(op =='Q')
{
cout<<query(str)<<endl;
}
}
return 0;
}