AcWing 835. Trie字符串统计
原题链接
简单
作者:
xi.xi
,
2025-04-14 15:54:50
· 四川
,
所有人可见
,
阅读 2
#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';
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;
p = son[p][u];
}
return cnt[p];
}
int main(){
int n;
cin>>n;
while(n--){
char op;
cin>>op;
scanf("%s",str);
if(op=='I') insert(str);
else cout<<query(str)<<endl;
}
return 0;
} ![Trie树.png](https: