AcWing 835. Trie字符串统计
原题链接
简单
题目描述
样例
#include <iostream>
using namespace std;
const int N=100010;
char str[N];
int son[N][26],cnt[N];
int idx,n;
//插入一个字符串
void insert(char *str){
int p=0;//节点下标
for(int i=0;str[i];i++){
int u=str[i]-'a';//p结点的孩子结点
if(!son[p][u]) son[p][u]=++idx;//不存在就创建
p=son[p][u];
}
cnt[p]++;//最后一个字符出现的次数
}
//查询字符串是否出现以及出现了几次
int query(char *str){//注意这里的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(){
cin>>n;
while(n--){
char op[2];
scanf("%s%s",op,str);
if(op[0]=='I'){
insert(str);
}else{
cout<<query(str)<<endl;
}
}
return 0;
}