AcWing 835. Trie字符串统计
原题链接
简单
C++ 代码
#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]==0) son[p][u]=++idx;
p=son[p][u];
}
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]==0) return 0;
p=son[p][u];
}
return cnt[p];
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
char op;
cin>>op>>str;
if (op=='I'){
insert(str);
}else{
printf("%d\n",query(str));
}
}
return 0;
}