SHARE
TWEET

TRIE TREE

jakaria_hossain May 7th, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct node {
  4.     bool endmark;
  5.     node* next[26 + 1];
  6.     node()
  7.     {
  8.         endmark = false;
  9.         for (int i = 0; i < 26; i++)
  10.             next[i] = NULL;
  11.     }
  12. } * root;
  13. void insert(char* str, int len)
  14. {
  15.     node* curr = root;
  16.     for (int i = 0; i < len; i++) {
  17.         int id = str[i] - 'a';
  18.         if (curr->next[id] == NULL)
  19.             curr->next[id] = new node();
  20.         curr = curr->next[id];
  21.     }
  22.     curr->endmark = true;
  23. }
  24. bool search(char* str, int len)
  25. {
  26.     node* curr = root;
  27.     for (int i = 0; i < len; i++) {
  28.         int id = str[i] - 'a';
  29.         if (curr->next[id] == NULL)
  30.             return false;
  31.         curr = curr->next[id];
  32.     }
  33.     return curr->endmark;
  34. }
  35. void del(node* cur)
  36. {
  37.     for (int i = 0; i < 26; i++)
  38.         if (cur->next[i])
  39.             del(cur->next[i]);
  40.  
  41.     delete (cur);
  42. }
  43. int main()
  44. {
  45.  
  46.     puts("ENTER NUMBER OF WORDS");
  47.     root = new node();
  48.     int num_word;
  49.     cin >> num_word;
  50.     for (int i = 1; i <= num_word; i++) {
  51.         char str[50];
  52.         scanf("%s", str);
  53.         insert(str, strlen(str));
  54.     }
  55.     printf("ENTER NUMBER OF QUERY\n");
  56.     int query;
  57.     cin >> query;
  58.     for (int i = 1; i <= query; i++) {
  59.         char str[50];
  60.         scanf("%s", str);
  61.         if (search(str, strlen(str)))
  62.             puts("FOUND");
  63.         else
  64.             puts("NOT FOUND");
  65.     }
  66.     del(root);
  67.     return 0;
  68. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top