AcWing 835. Trie字符串统计
原题链接
简单
作者:
云_580
,
2024-09-08 16:31:23
,
所有人可见
,
阅读 1
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,idx;
int son[N][26],cnt[N];
void insert(string s){
int p = 0;
for(int i = 0;s[i];i++){
int u = s[i]-'a';
//如果没有这个子节点,就创建一个子节点
if(!son[p][u])son[p][u]=++idx;
//然后走上去
p=son[p][u];
}
cnt[p]++;
//标记一下
}
int query(string s){
int p = 0;
for(int i = 0;s[i];i++){
int u = s[i]-'a';
if(!son[p][u])return 0;
p = son[p][u];
}
return cnt[p];
}
int main(){
cin>>n;
for(int i = 1;i<=n;i++){
char ch;
string s;
cin>>ch>>s;
if(ch=='I')insert(s);
else cout<<query(s)<<endl;;
}
return 0;
}