Advertisement
oleg_drawer

Untitled

Apr 20th, 2020
307
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.31 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct node{
  5.     bool term = false;
  6.     int ind;
  7.     node* lett[26];
  8.  
  9.     node(int ind){
  10.         this->ind = ind;
  11.         for(auto &l :lett)
  12.             l = nullptr;
  13.     }
  14.  
  15. };
  16.  
  17. node* root = new node(0);
  18. vector<node*>nodes = {root};
  19. int cnter = 1;
  20.  
  21. void add_to_bor(string s){
  22.     node* curr = nodes[0];
  23.     for(int i = 0; i < s.size(); i++){
  24.         char a = s[i];
  25.         if(curr->lett[a -'a'] == nullptr){
  26.             curr->lett[a -'a'] = new node(cnter);
  27.             curr = curr->lett[a -'a'];
  28.             nodes.push_back(curr);
  29.             cnter++;
  30.         }
  31.     }
  32.     curr->term = true;
  33. }
  34. bool check(string s){
  35.  
  36.     node* curr = nodes[0];
  37.     for(int i = 0; i < s.size(); i++){
  38.         if(curr->lett[s[i] - 'a'] == nullptr){
  39.             return false;
  40.         }
  41.         curr = curr->lett[s[i] - 'a'];
  42.     }
  43.     return curr->term;
  44.  
  45. }
  46.  
  47. bool check_substr(string s){
  48.  
  49.     node* curr = nodes[0];
  50.     for(int i = 0; i < s.size(); i++){
  51.         if(curr->lett[s[i] - 'a'] == nullptr){
  52.             return false;
  53.         }
  54.         curr = curr->lett[s[i] - 'a'];
  55.     }
  56.     return true;
  57.  
  58. }
  59.  
  60.  
  61. int main() {
  62.  
  63.     string text;
  64.     cin >> text;
  65.     for(int i = 0; i < text.size(); i++){
  66. //        string s = string(text.begin() + i, text.end());
  67. //        add_to_bor(s);
  68.         node* curr = nodes[0];
  69.         for(int j = i; j < text.size(); j++){
  70.             char a = text[j];
  71.             if(curr->lett[a -'a'] == nullptr){
  72.                 curr->lett[a -'a'] = new node(cnter);
  73.                 curr = curr->lett[a -'a'];
  74.                 nodes.push_back(curr);
  75.                 cnter++;
  76.             }
  77.         }
  78.         curr->term = true;
  79.  
  80.     }
  81.     int m;
  82.     cin >> m;
  83.     for(int i = 0; i < m; i++){
  84.         string s;
  85.         cin >> s;
  86.         if(check_substr(s))
  87.             cout << "Yes" << endl;
  88.         else
  89.             cout << "No" << endl;
  90.     }
  91.  
  92. //    string s;
  93. //    cin >> s;
  94. //    add_to_bor(s);
  95. //    while(cin >> s){
  96. //        cout << bool(check(s)) << endl;
  97. //    }
  98. //    string s1 = string(s.begin()+1, s.end());
  99. //    add_to_bor(s1);
  100. //    node * curr = new node(1);
  101. //    nods.push_back(curr);
  102. //
  103. //    curr->lett[0] = new node(2);
  104. //    curr = curr->lett[0];
  105. //    nods.push_back(curr);
  106.  
  107.  
  108.     return 0;
  109. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement