AcWing 835. Trie字符串统计
原题链接
简单
作者:
一只鳄鱼
,
2021-01-23 13:39:58
,
所有人可见
,
阅读 252
#include<bits/stdc++.h>
using namespace std;
const int N=20005;
int n;
int idx;//记录边数
int son[N][27];//son[i][0-26],第i条边与第0-26个字母之间连边的边的序号
int cnt[N];//第i条边末尾有没有结束的
//插入
void insert(string str)
{
int p=0;
for(int i=0;str[i];i++)
{
int u=str[i]-'a';
if(son[p][u]==0)
{
son[p][u]=++idx;//0条边是根节点
}
p=son[p][u];
}
cnt[p]++;
}
//查询
int query(string str)
{
bool flag=1;
int p=0;
for(int i=0;str[i];i++)
{
int u=str[i]-'a';
if(son[p][u]==0)
return 0;
p=son[p][u];
}
return cnt[p];
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
string op,x;
cin>>op>>x;
if(op=="I")
{
insert(x);
}
else
{
cout<<query(x)<<endl;
}
}
return 0;
}