Advertisement
Guest User

Untitled

a guest
Mar 22nd, 2018
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.00 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <time.h>
  5. #include <string.h>
  6. #include <cstring>
  7. #include <cmath>
  8. #include <algorithm>
  9. #include <queue>
  10. #include <stack>
  11. #include <cassert>
  12. #include <set>
  13. #include <vector>
  14. #include <map>
  15.  
  16. using namespace std;
  17.  
  18. const int N = 1111111;
  19. const int K = 26;
  20.  
  21. struct Node {
  22.     Node* son[K];
  23.     Node* go[K];
  24.     Node* parent;
  25.     Node* suff_link;
  26.     Node* up;
  27.     char char_to_parent;
  28.     bool is_leaf;
  29.     bool was_marked;
  30.     vector <int> leaf_number;
  31.     Node() {
  32.         for(int j = 0; j < K; ++j) {
  33.             son[j] = go[j] = nullptr;
  34.         }
  35.         parent = suff_link = up = nullptr;
  36.         is_leaf = was_marked = false;
  37.     }
  38. };
  39.  
  40. Node* root;
  41.  
  42. void add(string s, int number) {
  43.     Node* cur = root;
  44.     for(int i = 0; i < (int) s.size(); ++i) {
  45.         char c = s[i];
  46.         int k = c - 'a';
  47.         if(cur->son[k] == nullptr) {
  48.             cur->son[k] = new Node;
  49.             cur->son[k]->parent = cur;
  50.             cur->son[k]->char_to_parent = c;
  51.         }
  52.         cur = cur->son[k];
  53.     }
  54.     cur->is_leaf = true;
  55.     cur->leaf_number.push_back(number);
  56. }
  57.  
  58. Node* get_link(Node* v, char c);
  59. Node* get_suff_link(Node* v);
  60. Node* get_up(Node* v);
  61.  
  62. Node* get_link(Node* v, char c) {
  63.     int k = c - 'a';
  64.     if(v->go[k] == nullptr) {
  65.         if(v->son[k] != nullptr) {
  66.             v->go[k] = v->son[k];
  67.         } else
  68.         if(v == root) {
  69.             v->go[k] = root;
  70.         } else {
  71.             v->go[k] = get_link(get_suff_link(v), c);
  72.         }
  73.     }
  74.     return v->go[k];
  75. }
  76.  
  77. Node* get_suff_link(Node* v) {
  78.     if(v->suff_link == nullptr) {
  79.         if(v == root || v->parent == root) {
  80.             v->suff_link = root;
  81.         } else {
  82.             v->suff_link = get_link(get_suff_link(v->parent), v->char_to_parent);
  83.         }
  84.     }
  85.     return v->suff_link;
  86. }
  87.  
  88. Node* get_up(Node* v) {
  89.     if(v->up == nullptr) {
  90.         if(get_suff_link(v)->is_leaf) {
  91.             v->up = get_suff_link(v);
  92.         } else
  93.         if(get_suff_link(v) == root) {
  94.             v->up = root;
  95.         } else {
  96.             v->up = get_up(get_suff_link(v));
  97.         }
  98.     }
  99.     return v->up;
  100. }
  101.  
  102. bool ans[N];
  103.  
  104. int main(){
  105.  
  106.     freopen("dictionary.in", "r", stdin);
  107.     freopen("dictionary.out", "w", stdout);
  108.  
  109.  
  110.     string t;
  111.     cin >> t;
  112.  
  113.     root = new Node;
  114.     int n;
  115.     cin >> n;
  116.     for(int i = 0; i < n; ++i) {
  117.         string s;
  118.         cin >> s;
  119.         add(s, i);
  120.     }
  121.  
  122.     Node* cur = root;
  123.     for(int i = 0; i < (int) t.size(); ++i) {
  124.         char c = t[i];
  125.         cur = get_link(cur, c);
  126.         Node* temp = cur;
  127.         while(temp != root) {
  128.             if(temp->was_marked) break;
  129.             for(int x : temp->leaf_number) {
  130.                 ans[x] = true;
  131.             }
  132.             temp->was_marked = true;
  133.             temp = get_up(temp);
  134.         }
  135.     }
  136.  
  137.     for(int i = 0; i < n; ++i) {
  138.         cout << (ans[i] ? "Yes\n" : "No\n");
  139.     }
  140.  
  141.     return 0;
  142. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement