AcWing 835. Trie字符串统计
原题链接
简单
作者:
Chandler丶
,
2024-02-20 22:49:38
,
所有人可见
,
阅读 24
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <string>
using namespace std;
#define ll long long
const int N =100010;
//Trie字符统计
int son[N][26];//每个节点最多有26个子节点
int cnt[N]; //cnt存的是以当前节点结尾的字符串有多少个
int idx; //idx存的是当用用到的下标
//下标是0的节点即使根节点,又是空节点
char str[N];
void insert(char str[])
{
int p = 0; //表明从根节点开始
for(int i = 0; str[i]; i ++)
{
int u = str[i] - 'a';
if(!son[p][u]) son[p][u] = ++idx;//如果节点不存在就创建,这时 son[p][u]被赋值为1,Idx = 1;
p = son[p][u]; //更新p为最新存储的节点
}
cnt[p] ++;//遍历结束, 以当前节点结尾的字符串的数量加1;
}
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 t;
scanf("%d",&t);
while(t--)
{
char op[2];
scanf("%s%s",&op,&str);
if(op[0] == 'I')
{
insert(str);
}
else
{
printf("%d\n",query(str));
}
}
return 0;
}