Guest User

Untitled

a guest
Apr 27th, 2020
35
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.17 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment