AcWing 835. Trie字符串统计
原题链接
简单
作者:
刘杰
,
2024-02-23 10:06:18
,
所有人可见
,
阅读 34
//字典树 用来快速存储和查找字符串集合的结构 字符的类型不能太多
#include <iostream>
using namespace std;
const int N = 1e5+10;
int ne[N][26], cnt[N], idx; //字典树 26 字符集 cnt 存在次数统计, idx单词长度
char str[N]; //输入的字符串
void insert(char str[]){
int p = 0; //指针
for(int i = 0; str[i]; i++){
int u = str[i] - 'a';
if(!ne[p][u]) ne[p][u] = ++idx; //没有创建
p = ne[p][u]; //指向下一个节点
}
cnt[p]++;
}
int query(char str[]){
int p = 0;
for(int i =0; str[i]; i++){
int u = str[i] - 'a';
if(!ne[p][u]) return 0; //未找到
p = ne[p][u]; //指向下一个节点
}
return cnt[p];
}
int main(){
int n;
cin >> 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;
}