oleg_drawer

Untitled

May 2nd, 2020
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct node {
  6.     node* letters[26];
  7.     vector<int> has_ans;
  8.     node* suf_mail, *pred;
  9.     int last_symb;
  10.     node() {
  11.         fill(letters, letters + 26, nullptr);
  12.         suf_mail = nullptr;
  13.         pred = nullptr;
  14.         has_ans.clear();
  15.         last_symb = 1;
  16.     }
  17. };
  18.  
  19. void make_bor(node * now, string& s, int ind, int j) {
  20.     if (ind == (int) s.size()) {
  21.         now->has_ans.push_back(j);
  22.         return;
  23.     }
  24.     if (now->letters[s[ind] - 'a'] == nullptr) {
  25.         node* new_node = new node();
  26.         new_node->last_symb = s[ind] - 'a';
  27.         new_node->pred = now;
  28.         now->letters[s[ind] - 'a'] = new_node;
  29.     }
  30.     make_bor(now->letters[s[ind] - 'a'], s, ind + 1, j);
  31. }
  32.  
  33. set<node*> used;
  34. queue<node*> que;
  35. vector<int> ans;
  36.  
  37. void go(node * now, string& s, int ind) {
  38.     used.insert(now);
  39.     if (ind == (int) s.size()) {
  40.         return;
  41.     }
  42.     go(now->letters[s[ind] - 'a'], s, ind + 1);
  43. }
  44.  
  45. int main() {
  46.     ios_base::sync_with_stdio(0);
  47.     cin.tie(0);
  48.     node * root = new node();
  49.     root->pred = root;
  50.     int n;
  51.     cin >> n;
  52.     for (int i = 0; i < n; i++) {
  53.         string s1;
  54.         cin >> s1;
  55.         make_bor(root, s1, 0, i + 1);
  56.     }
  57.     root->suf_mail = root;
  58.     queue<node*> bfs;
  59.     bfs.push(root);
  60.     while (!bfs.empty()) {
  61.         node * next = bfs.front();
  62.         bfs.pop();
  63.         if (next == root) {
  64.             for (int i = 0; i < 26; i++) {
  65.                 if (next->letters[i] != nullptr) {
  66.                     bfs.push(next->letters[i]);
  67.                 } else {
  68.                     next->letters[i] = root;
  69.                 }
  70.             }
  71.             continue;
  72.         }
  73.         node * now = next->pred;
  74.         if (now == root) {
  75.             next->suf_mail = now;
  76.             for (int i = 0; i < 26; i++) {
  77.                 if (next->letters[i] != nullptr) {
  78.                     bfs.push(next->letters[i]);
  79.                 } else {
  80.                     next->letters[i] = next->suf_mail->letters[i];
  81.                 }
  82.             }
  83.             continue;
  84.         }
  85.         int next_char = next->last_symb;
  86.         next->suf_mail = next->pred->suf_mail->letters[next_char];
  87.         for (int i = 0; i < 26; i++) {
  88.             if (next->letters[i] != nullptr) {
  89.                 bfs.push(next->letters[i]);
  90.             } else {
  91.                 next->letters[i] = next->suf_mail->letters[i];
  92.             }
  93.         }
  94.     }
  95.     ans.resize(n);
  96.     string s;
  97.     cin >> s;
  98.     go(root, s, 0);
  99.     for (auto& i : used) {
  100.         que.push(i);
  101.     }
  102.     while (!que.empty()) {
  103.         node * now = que.front();
  104.         que.pop();
  105.         if (now->has_ans.size() != 0) {
  106.             for (unsigned int i = 0; i < now->has_ans.size(); i++) {
  107.                 ans[now->has_ans[i] - 1] = 1;
  108.             }
  109.         }
  110.         if (used.count(now->suf_mail) == 0) {
  111.             used.insert(now->suf_mail);
  112.             que.push(now->suf_mail);
  113.         }
  114.     }
  115.     for (int j = 0; j < n; ++j) {
  116.         if (ans[j] == 1) {
  117.             cout << "YES" << endl;
  118.         } else {
  119.             cout << "NO" << endl;
  120.         }
  121.     }
  122.     return 0;
  123. }
Add Comment
Please, Sign In to add comment