fork download 
  1. /// trie str by muoii
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define tag "spoj"
  6. #define maxn 0
  7. #define module 0
  8. #define oo 1000000007LL
  9. ///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  10. struct trie{
  11.     int visit,finish;
  12.     trie *next[26];
  13.  
  14.     void add(const string &s)
  15.     {
  16.         trie *ptr=this;
  17.  
  18.         for(int i=0,c;i<s.size();i++)
  19.         {
  20.             c=s[i]-'a';
  21.  
  22.             if(!(ptr->next[c])) ptr->next[c]=new trie();
  23.  
  24.             ptr=ptr->next[c];
  25.             ptr->visit++;
  26.         }
  27.         ptr->finish++;
  28.     }
  29.  
  30.     int check(const string &s)
  31.     {
  32.         trie *ptr=this;
  33.  
  34.         for(int i=0,c;i<s.size();i++)
  35.         {
  36.             c=s[i]-'a';
  37.  
  38.             if(!(ptr->next[c])) return 0;
  39.  
  40.             ptr=ptr->next[c];
  41.  
  42.         }
  43.         return ptr->finish;
  44.     }
  45.  
  46.     void delling(trie *ptr,const int &i,const string &s)
  47.     {
  48.         if(i==s.size())
  49.         {
  50.             ptr->finish--;
  51.             return;
  52.         }
  53.  
  54. 		trie* nxt=ptr->next[s[i]-'a'];
  55.  
  56.         delling(nxt,i+1,s);
  57.  
  58.         nxt->visit--;
  59.         if(nxt->visit==0)
  60. 		{
  61. 			delete(nxt);
  62. 			ptr->next[s[i]-'a']=0;
  63. 		}
  64.     }
  65.     void del(const string &s)
  66.     {
  67.         if(!check(s)) return;
  68.         delling(this,0,s);
  69.     }
  70.  
  71. } *root = new trie();
  72. int main()
  73. {
  74.     #ifdef dmdd
  75.     freopen(tag".inp","r",stdin); freopen(tag".out","w",stdout);
  76.     #endif // dmdd
  77.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  78.     int q;
  79.     string str;
  80.     int type;
  81.     cin>>q;
  82.     for(int i=0;i<q;i++)
  83.     {
  84.         cin>>type>>str;
  85.  
  86.         if(type==0) root->del(str);
  87.         else if(type==1) root->add(str);
  88.         else cout<<root->check(str)<<"\n";
  89.     }
  90.     return 0;
  91. }
  92.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
10
0 helo
1 hello
2 alo
1 helo
2 hello
1 alo
2 helo
0 helo
2 alo
2 helo
stdout 
0
1
1
1
0
https://ideone.com/OrY1R8
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!