AcWing 835. Trie字符串统计(详细注释版本)
原题链接
简单
作者:
Misakiii
,
2021-01-21 16:31:21
,
所有人可见
,
阅读 379
// 由于输入的字符串总长不超过10^5
// 所以二维数组的第一维不超过1e5(因为节点个数不超过1E5)
// 这里用的idx和链表里面用的idx一样
// 不需要重置为0,每次有新的东西插入就++idx给它分配一个新的下标
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
//son数组:第一维存总节点个数,由于节点数量不超过N,故为N
//第二维存其子节点,而一个节点最多有26个孩子
//son数组的值存得是某个节点的所有孩子,如son[0][1] = 1;表示根节点有一个孩子a节点
int son[N][26];
int cnt[N]; //存以当前这个点结尾的单词有多少个
int idx; //存当前用到了哪个下标,下标是0的点既是根节点又是空节点
//把str包含的字符串加入到树中
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; //如果p节点不存在u这个儿子,就创建出来
p = son[p][u]; //让p走到下一个点,也即是走到p的子节点
}
cnt[p]++; //表示以p为结尾的单词数量加一
}
//查询str单词是否在树中
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(){
int n;
cin >> n;
while(n--){
char op[2];
char s[N];
cin >> op;
if(*op == 'I') cin >> s, insert(s);
if(*op == 'Q') cin >> s, cout << query(s) << endl;
}
return 0;
}