AcWing 835. Trie字符串统计(链式写法)
原题链接
简单
作者:
JcKy
,
2021-06-08 16:42:19
,
所有人可见
,
阅读 214
C++ 代码
#include<iostream>
#include<string>
using namespace std;
class node{
public:
node* next[26];
int cnt;
public:
node():cnt(0){for(int i=0;i<26;++i) next[i]=nullptr;}
~node(){delete []*next;}
};
class Trie{
public:
node* n;
public:
Trie(){n=new node();}
void insert(const string& x){
node* root=n;
int len=x.size();
for(auto i:x){
if(root->next[i-'a']==nullptr){
root->next[i-'a']=new node();
}
root=root->next[i-'a'];
}
++root->cnt;
}
int query(const string& x){
node* root=n;
int len=0;
for(auto i:x){
int pos=i-'a';
if(root->next[pos]==nullptr){
break;
}
++len;
root=root->next[pos];
}
if(len!=x.size())
return 0;
return root->cnt;
}
};
int main(){
int n;
cin>>n;
Trie* t=new Trie();
while(n--){
string str;
char c;
cin>>c;
cin>>str;
if(c=='I'){
t->insert(str);
}else{
cout<<t->query(str)<<endl;
}
}
return 0;
}