Maruf_Hasan

TRIE

Apr 17th, 2020
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.32 KB | None | 0 0
  1. //In the Name of Allah Most Gracious, Most Merciful//
  2. /*If you want something you've never had, you have to do something you never did.*/
  3.  
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6.  
  7.  
  8. #define pb push_back
  9. #define ll long long
  10. #define pii pair<int,int>
  11. #define pll pair<ll,ll>
  12. #define M 100007
  13. #define INF 1e9
  14. #define INFL 1e18
  15. #define PI acos(-1)
  16. #define mp make_pair
  17. #define fast_in_out ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  18. //const int fx[]= {+1,-1,+0,+0};
  19. //const int fy[]= {+0,+0,+1,-1};
  20. //const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
  21. //const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
  22. //const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
  23. //const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
  24.  
  25. struct node
  26. {
  27. bool endmark;
  28. node* next[27];
  29. node()
  30. {
  31. endmark=false;
  32. for(int i=0;i<26;i++)
  33. {
  34. next[i]=NULL;
  35. }
  36. }
  37. }*root;
  38.  
  39.  
  40. void insertnode(string str,int len)
  41. {
  42. node* curr=root;
  43. for(int i=0;i<len;i++)
  44. {
  45. int id=str[i]-'a';
  46.  
  47. if(curr->next[id]==NULL)
  48. {
  49. curr->next[id]=new node();
  50. }
  51. curr=curr->next[id];
  52. }
  53.  
  54. curr->endmark=true;
  55. }
  56. bool searchstring(string str,int len)
  57. {
  58. node *curr=root;
  59.  
  60. for(int i=0;i<len;i++)
  61. {
  62. int id=str[i]-'a';
  63.  
  64. if(curr->next[id]==NULL)
  65. {
  66. return false;
  67. }
  68. curr=curr->next[id];
  69. }
  70. return curr->endmark;
  71. }
  72.  
  73.  
  74. void del(node* cur)
  75. {
  76. for(int i=0;i<26;i++)
  77. {
  78. if(cur->next[i])
  79. {
  80. del(cur->next[i]);
  81. }
  82. }
  83. delete (cur);
  84. }
  85.  
  86.  
  87.  
  88. int main()
  89. {
  90. fast_in_out;
  91. //freopen("input.txt","r",stdin);
  92. //freopen("output.txt","w",stdout);
  93. int n;
  94. cin>>n;
  95. // getchar();
  96. root=new node();
  97. for(int i=0;i<n;i++)
  98. {
  99. string a;
  100. cin>>a;
  101. insertnode(a,a.size());
  102. }
  103. cout<<"QUERY"<<endl;
  104. int q;
  105. cin>>q;
  106.  
  107. for(int i=0;i<q;i++)
  108. {
  109. string a;
  110. cin>>a;
  111. //cout<<str<<endl;
  112. if(searchstring(a,a.size()))
  113. {
  114. cout<<"FOUND"<<endl;
  115. }
  116. else
  117. {
  118. cout<<"NOT FOUND"<<endl;
  119. }
  120. }
  121. del(root);
  122. return 0;
  123. }
Advertisement
Add Comment
Please, Sign In to add comment