Advertisement
Guest User

Untitled

a guest
Feb 19th, 2020
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.47 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. struct node {
  5. bool endmark;
  6. node* next[26 + 1];
  7. node()
  8. {
  9. endmark = false;
  10. for (int i = 0; i < 26; i++)
  11. next[i] = NULL;
  12. }
  13. } * root;
  14. void insert(char* str, int len)
  15. {
  16. node* curr = root;
  17. for (int i = 0; i < len; i++) {
  18. int id = str[i] - 'a';
  19. if (curr->next[id] == NULL)
  20. curr->next[id] = new node();
  21. curr = curr->next[id];
  22. }
  23. curr->endmark = true;
  24. }
  25. bool search(char* str, int len)
  26. {
  27. node* curr = root;
  28. for (int i = 0; i < len; i++) {
  29. int id = str[i] - 'a';
  30. if (curr->next[id] == NULL)
  31. return false;
  32. curr = curr->next[id];
  33. }
  34. return curr->endmark;
  35. }
  36. void del(node* cur)
  37. {
  38. for (int i = 0; i < 26; i++)
  39. if (cur->next[i])
  40. del(cur->next[i]);
  41.  
  42. delete (cur);
  43. }
  44. int main()
  45. {
  46.  
  47. puts("ENTER NUMBER OF WORDS");
  48. root = new node();
  49. int num_word;
  50. cin >> num_word;
  51. for (int i = 1; i <= num_word; i++) {
  52. char str[50];
  53. scanf("%s", str);
  54. insert(str, strlen(str));
  55. }
  56. puts("ENTER NUMBER OF QUERY";);
  57. int query;
  58. cin >> query;
  59. for (int i = 1; i <= query; i++) {
  60. char str[50];
  61. scanf("%s", str);
  62. if (search(str, strlen(str)))
  63. puts("FOUND");
  64. else
  65. puts("NOT FOUND");
  66. }
  67. del(root);
  68. return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement