AcWing 835. Trie字符串统计
原题链接
简单
作者:
心之所向_7
,
2023-01-10 16:28:08
,
所有人可见
,
阅读 110
#include<iostream>
using namespace std;
const int N=100010;
int son[N][26],cnt[N],idx;
char str[N];
void insert(char str[])
{
int p=0;//当前节点为根节点
for(int i=0;str[i];i++)
{
int u=str[i]-'a';//将字母映射为0~25
if(!son[p][u])son[p][u]=++idx;//如果没有子节点创建一个子节点
p=son[p][u];//指向该子节点
}
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;//如果没有查找到该节点返回0
p=son[p][u];//如果存在子节点则指向子节点
}
return cnt[p];//返回查找到的字符串数量
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
char op[2];
scanf("%s%s",op,str);
if(op[0]=='I')insert(str);
else printf("%d\n",query(str));
}
return 0;
}