jakaria_hossain

TRIE TREE

May 7th, 2019
85
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