fork(2) download
copy 
  1. #include<iostream>
  2. #include<string.h>
  3. #include<stdlib.h>
  4. using namespace std;
  5.  
  6. struct trie_node{
  7. int value;
  8. trie_node *child[27];
  9. };
  10.  
  11. struct trie{
  12.  struct trie_node *root;
  13.  int count;
  14. };
  15.  
  16. trie_node * getnode()
  17. {
  18.    // trie_node *ptrie=new trie_node;
  19.    trie_node *ptrie = (trie_node *)malloc(sizeof(struct trie_node));
  20.    if(ptrie)
  21.    {
  22.     ptrie->value=0;
  23.     for(int i=0;i<27;i++)
  24.     ptrie->child[i]=NULL;
  25.    }
  26.     return ptrie;
  27. }
  28.  
  29. void init(struct trie **t)
  30. {
  31.    (*t)->root=getnode();
  32.    (*t)->count=0; 
  33. }
  34.  
  35. void insert(struct trie **t, char key[])
  36. {
  37.  
  38.     (*t)->count++;
  39.     trie_node *p ;
  40.     p=(*t)->root;
  41.  
  42.     int len=strlen(key);
  43.     int i;
  44.     for(i=0;i<27;i++)
  45.      {
  46.      //	if(p->child[i]==NULL)
  47.      //	cout<<"Y ";
  48.      //	else cout<<"N ";
  49.      }
  50.   //   cout<<endl;
  51.     for(i=0;i<len;i++)
  52.     {
  53.         int idx=key[i]-'a';
  54.       //  cout<<" "<<key[i]<<": ";
  55.         if(!(p->child[idx]))
  56.         {
  57.         //	cout<<idx;
  58.             p->child[idx]=getnode();
  59.         }
  60.         p=p->child[idx];
  61.     }
  62.    // cout<<endl;
  63.     p->value=(*t)->count;
  64. }
  65.  
  66. bool search(struct trie* t, char key[])
  67. {
  68.     int len=strlen(key);
  69.     int i;
  70.     struct trie_node *p= (t)->root;
  71.     for(i=0;i<len;i++)
  72.     {
  73.         int check= (int)key[i]-(int)'a';
  74.         if(!(p->child[check]))
  75.         return 1;
  76.  
  77.         p=p->child[check];
  78.     }
  79.  
  80.     return 0;
  81. }
  82.  
  83. int main()
  84. {
  85.     char key[][6]={"hi", "hello", "you", "ekta", "me"};
  86.     trie *t;
  87.     init(&t);
  88.     int i;
  89.     for(i=0;i<5;i++)
  90.      insert(&t,key[i]);
  91.  
  92.      char output[][4]={"YES", "NO"};
  93.  
  94.      cout<<output[search(t, "me")]<<endl;
  95.     return 0;
  96. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
YES
https://ideone.com/yHwg0G
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

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!