AcWing 835. Trie字符串统计
原题链接
简单
作者:
术
,
2021-01-07 15:19:47
,
所有人可见
,
阅读 275
#include <iostream>
using namespace std;
const int N=100005;
int cnt[N];
int son[N][26];
int idx;
void insert(char str[]){
int p=0;
for(int i=0;str[i];i++){
int t=str[i]-'a';
if(!son[p][t]) son[p][t]=++idx;
p=son[p][t];
}
cnt[p]++;
}
int ans(char str[]){
int p=0;
for(int i=0;str[i];i++){
int t=str[i]-'a';
p=son[p][t];
}
return cnt[p];
}
int main()
{
int n;
cin>>n;
while(n--){
char query[2];
char str[N];
cin>>query>>str;
if(query[0]=='I') insert(str);
else cout<<ans(str)<<endl;
}
//cout << "Hello world!" << endl;
return 0;
}