fork download
copy 
  1.  
  2. /// Trie (normal)...
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. #define ll long long
  7. #define maxn 5000050
  8.  
  9. struct Trie
  10. {
  11.     ll nextt[maxn][26];
  12.     ll endmark[maxn];
  13.     ll sz;
  14.     Trie()
  15.     {
  16.         clear();
  17.     }
  18.     void clear()
  19.     {
  20.         sz=0;
  21.         memset(nextt[0],-1,sizeof(nextt[0]));
  22.         memset(endmark,0,sizeof endmark);
  23.     }
  24.     void add(const char* str)
  25.     {
  26.         ll v=0;
  27.         ll len=strlen(str);
  28.         for(ll i = 0; i< len; ++i)
  29.         {
  30.             int id = str[i] - 'a';
  31.             if(nextt[v][id] == -1)
  32.             {
  33.                 nextt[v][id]=++sz;
  34.                 memset(nextt[sz],-1,sizeof(nextt[sz]));
  35.             }
  36.             v=nextt[v][id];
  37.         }
  38.         endmark[v]++;
  39.     }
  40.     ll dfs(const char* s)
  41.     {
  42.         ll v=0;
  43.         ll len=strlen(s);
  44.         for(ll i=0; i<len ; i++)
  45.         {
  46.             ll id=s[i]-'a';
  47.             if(nextt[v][id]==-1)
  48.             {
  49.                 return 0;
  50.             }
  51.             v=nextt[v][id];
  52.         }
  53.         return endmark[v];
  54.     }
  55. };
  56. Trie tree;
  57.  
  58. char s[100005];
  59. int main()
  60. {
  61.     tree.clear();
  62.     scanf(" %s",s);
  63.     tree.add(s);
  64.     tree.add(s);
  65.     cout<<tree.dfs(s)<<endl;
  66.     return 0;
  67. }
  68.  
Success #stdin #stdout 0.02s 42632KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
https://ideone.com/4pHr3C
language:
C++14 (gcc 8.3)
created:
3 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!