Advertisement
Guest User

Untitled

a guest
Jan 17th, 2020
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.46 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <set>
  5. #include <map>
  6.  
  7. using namespace std;
  8. vector<vector<int>> trie(1000000 + 100, vector<int>(27, -1));
  9. int m = 1;
  10. int root = 0;
  11. set<int> T;
  12. vector<pair<int, int>> p(1000000 + 100);
  13. vector<int> suf_link(1000000 + 100);
  14. map<int, string> term;
  15. vector<bool> used(1000000 + 100, false);
  16.  
  17. void insert(string &s) {
  18. auto v = root;
  19. for (auto c : s) {
  20. if (trie[v][c - 'a'] == -1) {
  21. trie[v][c - 'a'] = m++;
  22. p[m - 1] = {v, c};
  23. }
  24. v = trie[v][c - 'a'];
  25. }
  26. term[v] = s;
  27. T.insert(v);
  28. }
  29.  
  30. void make_suffix_links() {
  31. suf_link[root] = root;
  32. queue<int> q;
  33. for (int i = 0; i < 27; i++) {
  34. if (trie[root][i] != -1) {
  35. for (int j = 0; j < 27; j++) if (trie[trie[root][i]][j] != -1) q.push(trie[trie[root][i]][j]);
  36. suf_link[trie[root][i]] = root;
  37. }
  38. }
  39.  
  40. while (!q.empty()) {
  41. auto t = q.front();
  42. q.pop();
  43. auto pp = p[t];
  44. auto next = suf_link[pp.first];
  45. while (next != root && trie[next][pp.second - 'a'] == -1) {
  46. next = suf_link[next];
  47. }
  48. if (trie[next][pp.second - 'a'] == -1) suf_link[t] = root;
  49. else suf_link[t] = trie[next][pp.second - 'a'];
  50. for (int i = 0; i < 27; i++) {
  51. if (trie[t][i] != -1)
  52. q.push(trie[t][i]);
  53. }
  54. }
  55. }
  56.  
  57. int main() {
  58. freopen("search4.in", "r", stdin);
  59. freopen("search4.out", "w", stdout);
  60. int n;
  61. vector<string> strings;
  62. cin >> n;
  63. for (int i = 0; i < n; i++) {
  64. string s;
  65. cin >> s;
  66. insert(s);
  67. strings.emplace_back(s);
  68. }
  69.  
  70. make_suffix_links();
  71. string t;
  72. cin >> t;
  73. int cur = root;
  74. set<int> ans;
  75. for (auto &ch : t) {
  76. while (trie[cur][ch - 'a'] == -1 && cur != root) {
  77. cur = suf_link[cur];
  78. }
  79. if (trie[cur][ch - 'a'] != -1)
  80. cur = trie[cur][ch - 'a'];
  81. auto go = cur;
  82. while (go != root && !used[go]) {
  83. used[go] = true;
  84. if (T.count(go) > 0) {
  85. ans.insert(go);
  86. }
  87. go = suf_link[go];
  88. }
  89. }
  90. set<string> res;
  91. for (auto &cc : ans) {
  92. res.insert(term[cc]);
  93. }
  94. for (auto &s : strings) {
  95. (res.count(s) == 0 ? cout << "NO\n" << endl : cout << "YES\n" );
  96. }
  97. return 0;
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement