Advertisement
Guest User

Untitled

a guest
Sep 22nd, 2019
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.83 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #pragma comment(linker, "/STACK:256000000")
  3. #include <bits/stdc++.h>
  4.  
  5. #ifdef _DEBUG
  6. #include "optimization.h"
  7. #endif
  8.  
  9. using namespace std;
  10.  
  11. typedef long long ll;
  12. typedef unsigned long long ull;
  13. typedef pair<ll, ll> pll;
  14. typedef pair<int, int> pii;
  15.  
  16. #define TASK "tree"
  17. #define X first
  18. #define Y second
  19. #define inb push_back
  20. #define y1 dfsdfsd
  21.  
  22. class Aho
  23. {
  24. public:
  25. vector<vector<int>> go;
  26. vector<bool> term;
  27. vector<int> suf;
  28. Aho()
  29. {
  30. go.inb(vector<int>(100)), go.inb(vector<int>(100)), term.inb(0), term.inb(0), suf.inb(0), suf.inb(0);
  31. }
  32. void add(char *&s, int i)
  33. {
  34. int v = 1;
  35. int x = strlen(s);
  36. for (int i = 0; i < x; ++i)
  37. {
  38. int c = s[i] - ' ';
  39. if (!go[v][c]) go[v][c] = go.size(), go.inb(vector<int>(100)), term.inb(0), suf.inb(0);
  40. v = go[v][c];
  41. }
  42. term[v] = 1;
  43. }
  44. void bfs()
  45. {
  46. queue<int> q;
  47. q.push(1);
  48. while (q.size())
  49. {
  50. int v = q.front();
  51. q.pop();
  52. for (int c = 0; c < 100; ++c)
  53. {
  54. int u = (v == 1 ? 1 : go[suf[v]][c]);
  55. if (go[v][c])
  56. {
  57. suf[go[v][c]] = u;
  58. q.push(go[v][c]);
  59. }
  60. else
  61. go[v][c] = u;
  62. }
  63. term[v] = max(term[v], term[suf[v]]);
  64. }
  65. }
  66. bool get(char *&s)
  67. {
  68. int x = strlen(s);
  69. int v = 1;
  70. for (int i = 0; i < x; ++i)
  71. {
  72. int c = s[i] - ' ';
  73. if (!go[v][c]) return 0;
  74. v = go[v][c];
  75. if (term[v]) return 1;
  76. }
  77. return 0;
  78. }
  79. };
  80.  
  81. int main()
  82. {
  83. #ifdef _DEBUG
  84. freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  85. #else
  86. //freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  87. //freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
  88. #endif
  89. char *a, *s;
  90. a = new char[100];
  91. s = new char[300];
  92. int m;
  93. m = readInt();
  94. Aho d;
  95. for (int i = 0; i < m; ++i)
  96. {
  97. readLine(a);
  98. d.add(a, i);
  99. }
  100. d.bfs();
  101. while (!isEof())
  102. {
  103. readLine(s);
  104. if (d.get(s)) writeWord(s), writeChar('\n');
  105. }
  106. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement