Advertisement
Guest User

Untitled

a guest
Sep 22nd, 2019
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.58 KB | None | 0 0
  1. #pragma GCC optimize("O3")
  2. #include <iostream>
  3. #include <string>
  4. #include <vector>
  5.  
  6. int power_alph = 26;
  7.  
  8. struct vertex
  9. {
  10. std::vector<int> next; //следующие вершины
  11. bool leaf; //терминал ли
  12. int p; //вершина родитель
  13. char pch; //значение по которому перешли
  14. int link; //суффиксная ссылка
  15. int up; //сжатая суффиксная сслыка
  16. std::vector<int> go; //массив переходов
  17. std::vector<int> leafPatNumb;
  18.  
  19. vertex(int patterns_length)
  20. {
  21. next.assign(power_alph, -1);
  22. leaf = false;
  23. up = link = -1;
  24. go.assign(power_alph, -1);
  25. }
  26. };
  27.  
  28. struct Bohr
  29. {
  30. public:
  31. Bohr(std::vector<std::string> s, std::vector<int> l, int text_sz, int pat_size) : _patterns(std::move(s)),
  32. _length(std::move(l)), _size(1), _pat_size(pat_size)
  33. {
  34. _count.assign(text_sz, 0);
  35. _tree.emplace_back(pat_size);
  36. _tree[0].p = _tree[0].link = _tree[0].up = 0;
  37.  
  38. for (int i = 0; i < _patterns.size(); ++i)
  39. {
  40. add_string(_patterns[i], i);
  41. }
  42. }
  43. void add_string(const std::string &s, int patNum)
  44. {
  45. int cur_vertex = 0;
  46. for (int i = 0; i < s.size(); ++i)
  47. {
  48. char c = s[i] - 'a';
  49. if (_tree[cur_vertex].next[c] == -1)
  50. {
  51. _tree.emplace_back(_pat_size);
  52. _tree[_size].p = cur_vertex;
  53. _tree[_size].pch = s[i];
  54. _tree[cur_vertex].next[c] = _size++;
  55. }
  56. cur_vertex = _tree[cur_vertex].next[c];
  57. }
  58. _tree[cur_vertex].leaf = true;
  59. _tree[cur_vertex].leafPatNumb.push_back(patNum);
  60. }
  61.  
  62. int get_suff_link(int vertex)
  63. {
  64. if (_tree[vertex].link == -1)
  65. {
  66. if (!vertex || !_tree[vertex].p)
  67. {
  68. _tree[vertex].link = 0;
  69. }
  70. else
  71. {
  72. _tree[vertex].link = get_link(get_suff_link(_tree[vertex].p), _tree[vertex].pch);
  73. }
  74. }
  75. return _tree[vertex].link;
  76. }
  77.  
  78. int get_link(int vertex, char c)
  79. {
  80. if (_tree[vertex].go[c - 'a'] == -1)
  81. {
  82. if (_tree[vertex].next[c - 'a'] != -1)
  83. {
  84. _tree[vertex].go[c - 'a'] = _tree[vertex].next[c - 'a'];
  85. }
  86. else if (!vertex)
  87. {
  88. _tree[vertex].go[c - 'a'] = 0;
  89. }
  90. else
  91. {
  92. _tree[vertex].go[c - 'a'] = get_link(get_suff_link(vertex), c);
  93. }
  94. }
  95.  
  96. return _tree[vertex].go[c - 'a'];
  97. }
  98.  
  99. int get_up(int vertex)
  100. {
  101. if (_tree[vertex].up == -1)
  102. {
  103. if (_tree[get_suff_link(vertex)].leaf)
  104. {
  105. _tree[vertex].up = get_suff_link(vertex);
  106. }
  107. else if (!get_suff_link(vertex))
  108. {
  109. _tree[vertex].up = 0;
  110. }
  111. else
  112. {
  113. _tree[vertex].up = get_up(get_suff_link(vertex));
  114. }
  115. }
  116. return _tree[vertex].up;
  117. }
  118.  
  119. void check(int v, int i)
  120. {
  121. for (int u = v; u != 0; u = get_up(u))
  122. {
  123. if (_tree[u].leaf)
  124. for (auto j : _tree[u].leafPatNumb)
  125. {
  126. //std::cout << i - _patterns[j].length() << " " << _patterns[j] << std::endl;
  127. int k = i - _length[j]- _patterns[j].length();
  128. if (k >= 0)
  129. _count[k]++;
  130. }
  131. }
  132. }
  133.  
  134. void findAllPos(const std::string& s)
  135. {
  136. _text_size = s.size();
  137. int curVertex = 0;
  138. for(int i = 0; i < s.length(); i++)
  139. {
  140. curVertex = get_link(curVertex, s[i]);
  141. check(curVertex, i + 1);
  142. }
  143. }
  144.  
  145. void answer()
  146. {
  147. for (int i = 0; i < _count.size(); ++i)
  148. {
  149. if (_count[i] == _length.size() && _text_size - i >= _pat_size)
  150. std::cout << i << " ";
  151. }
  152. }
  153. private:
  154. std::vector<vertex> _tree;
  155. int _size;
  156. std::vector<std::string> _patterns;
  157. std::vector<int> _length;
  158. std::vector<int> _count;
  159. int _pat_size;
  160. int _text_size;
  161. };
  162.  
  163. int main() {
  164. std::ios_base::sync_with_stdio(0);
  165. std::cin.tie(0);
  166. std::cout.tie(0);
  167. std::vector<std::string> patterns;
  168. std::vector<int> length;
  169.  
  170. std::string current_pattern;
  171. int current_length = 0;
  172. //char c = getchar();
  173. std::string pattern;
  174. std::cin >> pattern;
  175. for(int i = 0; i < pattern.size(); ++i)
  176. {
  177. if (pattern[i] == '?')
  178. {
  179. if (!current_pattern.empty())
  180. {
  181. patterns.push_back(current_pattern);
  182. length.push_back(current_length - current_pattern.size());
  183. current_pattern.clear();
  184. }
  185. }
  186. else
  187. {
  188. current_pattern.push_back(pattern[i]);
  189. }
  190. //pattern[i] = getchar();
  191. current_length++;
  192. }
  193. if (!current_pattern.empty())
  194. {
  195. patterns.push_back(current_pattern);
  196. length.push_back(current_length - current_pattern.size());
  197. }
  198.  
  199. std::string text;
  200. std::cin >> text;
  201.  
  202. Bohr borrr(patterns, length, text.size(), current_length);
  203.  
  204. borrr.findAllPos(text);
  205. borrr.answer();
  206. return 0;
  207. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement