AcWing 835. Trie字符串统计
原题链接
简单
作者:
dsyami
,
2021-05-12 11:36:53
,
所有人可见
,
阅读 206
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int son[N][26], idx; //son存储Trie树,第一维是当前节点父节点的idx值,第二维是当前节点的idx值
int cnt[N]; //cnt数组记录以某个字符结尾的字符串的数量,即该字符串出现的次数
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; //如果这个字符未加入Trie树,则将当前idx插入树中
p = son[p][u]; //获取当前节点idx值,即为当前节点子节点的父节点的idx值
}
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;
p = son[p][u];
}
return cnt[p];
}
int main()
{
char str[N], op[2];
int n;
cin >> n;
while(n -- )
{
scanf("%s%s", op, str);
if(op[0] == 'I') insert(str);
else if(op[0] == 'Q') cout << query(str) << endl;
}
return 0;
}