Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("O3")
- #include <iostream>
- #include <string>
- #include <vector>
- int power_alph = 26;
- struct vertex
- {
- std::vector<int> next; //следующие вершины
- bool leaf; //терминал ли
- int p; //вершина родитель
- char pch; //значение по которому перешли
- int link; //суффиксная ссылка
- int up; //сжатая суффиксная сслыка
- std::vector<int> go; //массив переходов
- std::vector<int> leafPatNumb;
- vertex(int patterns_length)
- {
- next.assign(power_alph, -1);
- leaf = false;
- up = link = -1;
- go.assign(power_alph, -1);
- }
- };
- struct Bohr
- {
- public:
- Bohr(std::vector<std::string> s, std::vector<int> l, int text_sz, int pat_size) : _patterns(std::move(s)),
- _length(std::move(l)), _size(1), _pat_size(pat_size)
- {
- _count.assign(text_sz, 0);
- _tree.emplace_back(pat_size);
- _tree[0].p = _tree[0].link = _tree[0].up = 0;
- for (int i = 0; i < _patterns.size(); ++i)
- {
- add_string(_patterns[i], i);
- }
- }
- void add_string(const std::string &s, int patNum)
- {
- int cur_vertex = 0;
- for (int i = 0; i < s.size(); ++i)
- {
- char c = s[i] - 'a';
- if (_tree[cur_vertex].next[c] == -1)
- {
- _tree.emplace_back(_pat_size);
- _tree[_size].p = cur_vertex;
- _tree[_size].pch = s[i];
- _tree[cur_vertex].next[c] = _size++;
- }
- cur_vertex = _tree[cur_vertex].next[c];
- }
- _tree[cur_vertex].leaf = true;
- _tree[cur_vertex].leafPatNumb.push_back(patNum);
- }
- int get_suff_link(int vertex)
- {
- if (_tree[vertex].link == -1)
- {
- if (!vertex || !_tree[vertex].p)
- {
- _tree[vertex].link = 0;
- }
- else
- {
- _tree[vertex].link = get_link(get_suff_link(_tree[vertex].p), _tree[vertex].pch);
- }
- }
- return _tree[vertex].link;
- }
- int get_link(int vertex, char c)
- {
- if (_tree[vertex].go[c - 'a'] == -1)
- {
- if (_tree[vertex].next[c - 'a'] != -1)
- {
- _tree[vertex].go[c - 'a'] = _tree[vertex].next[c - 'a'];
- }
- else if (!vertex)
- {
- _tree[vertex].go[c - 'a'] = 0;
- }
- else
- {
- _tree[vertex].go[c - 'a'] = get_link(get_suff_link(vertex), c);
- }
- }
- return _tree[vertex].go[c - 'a'];
- }
- int get_up(int vertex)
- {
- if (_tree[vertex].up == -1)
- {
- if (_tree[get_suff_link(vertex)].leaf)
- {
- _tree[vertex].up = get_suff_link(vertex);
- }
- else if (!get_suff_link(vertex))
- {
- _tree[vertex].up = 0;
- }
- else
- {
- _tree[vertex].up = get_up(get_suff_link(vertex));
- }
- }
- return _tree[vertex].up;
- }
- void check(int v, int i)
- {
- for (int u = v; u != 0; u = get_up(u))
- {
- if (_tree[u].leaf)
- for (auto j : _tree[u].leafPatNumb)
- {
- //std::cout << i - _patterns[j].length() << " " << _patterns[j] << std::endl;
- int k = i - _length[j]- _patterns[j].length();
- if (k >= 0)
- _count[k]++;
- }
- }
- }
- void findAllPos(const std::string& s)
- {
- _text_size = s.size();
- int curVertex = 0;
- for(int i = 0; i < s.length(); i++)
- {
- curVertex = get_link(curVertex, s[i]);
- check(curVertex, i + 1);
- }
- }
- void answer()
- {
- for (int i = 0; i < _count.size(); ++i)
- {
- if (_count[i] == _length.size() && _text_size - i >= _pat_size)
- std::cout << i << " ";
- }
- }
- private:
- std::vector<vertex> _tree;
- int _size;
- std::vector<std::string> _patterns;
- std::vector<int> _length;
- std::vector<int> _count;
- int _pat_size;
- int _text_size;
- };
- int main() {
- std::ios_base::sync_with_stdio(0);
- std::cin.tie(0);
- std::cout.tie(0);
- std::vector<std::string> patterns;
- std::vector<int> length;
- std::string current_pattern;
- int current_length = 0;
- //char c = getchar();
- std::string pattern;
- std::cin >> pattern;
- for(int i = 0; i < pattern.size(); ++i)
- {
- if (pattern[i] == '?')
- {
- if (!current_pattern.empty())
- {
- patterns.push_back(current_pattern);
- length.push_back(current_length - current_pattern.size());
- current_pattern.clear();
- }
- }
- else
- {
- current_pattern.push_back(pattern[i]);
- }
- //pattern[i] = getchar();
- current_length++;
- }
- if (!current_pattern.empty())
- {
- patterns.push_back(current_pattern);
- length.push_back(current_length - current_pattern.size());
- }
- std::string text;
- std::cin >> text;
- Bohr borrr(patterns, length, text.size(), current_length);
- borrr.findAllPos(text);
- borrr.answer();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement