Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <vector>
- #include <array>
- #include <tuple>
- namespace
- {
- constexpr int g_uninitialized = -1;
- constexpr int ord_shift = -97;
- constexpr int alphabet_size = 26;
- } // namespace
- struct vertex
- {
- std::array<int, alphabet_size> next;
- std::array<int, alphabet_size> go;
- int parent;
- char parent_char;
- int link;
- int short_link;
- std::vector<int> entry_list;
- bool is_terminal;
- vertex()
- {
- for (int& edge : next)
- edge = g_uninitialized;
- for (int& elem : go)
- elem = g_uninitialized;
- parent = g_uninitialized;
- link = g_uninitialized;
- short_link = g_uninitialized;
- is_terminal = false;
- }
- };
- void add_string(const std::string str, const size_t s_len, std::vector<vertex>& trie,
- int& trie_size, const int entry_pos)
- {
- int v = 0;
- for (int c_idx = 0, i = 0; i < s_len; ++i)
- {
- c_idx = static_cast<int>(str[i]) + ord_shift;
- if (trie[v].next[c_idx] == g_uninitialized)
- {
- trie[v].next[c_idx] = trie_size;
- ++trie_size;
- vertex buff;
- buff.parent = v;
- buff.parent_char = str[i];
- trie.push_back(buff);
- }
- v = trie[v].next[c_idx];
- }
- trie[v].is_terminal = true;
- trie[v].entry_list.push_back(entry_pos);
- }
- int get_link(const int v, const char c, std::vector<vertex>& trie);
- int get_suff_link(const int v, std::vector<vertex>& trie)
- {
- if (trie[v].link == g_uninitialized)
- {
- if (v == 0 || trie[v].parent == 0)
- {
- trie[v].link = 0;
- }
- else
- {
- trie[v].link = get_link(get_suff_link(trie[v].parent, trie), trie[v].parent_char, trie);
- }
- }
- return trie[v].link;
- }
- int get_link(const int v, const char c, std::vector<vertex>& trie)
- {
- int c_idx = static_cast<int>(c) + ord_shift;
- if (trie[v].go[c_idx] == g_uninitialized)
- {
- if (trie[v].next[c_idx] != g_uninitialized)
- {
- trie[v].go[c_idx] = trie[v].next[c_idx];
- }
- else if (v == 0)
- {
- trie[v].go[c_idx] = 0;
- }
- else
- {
- trie[v].go[c_idx] = get_link(get_suff_link(v, trie), c, trie);
- }
- }
- return trie[v].go[c_idx];
- }
- int get_short_link(const int v, std::vector<vertex>& trie)
- {
- if (trie[v].short_link == g_uninitialized)
- {
- int u = get_suff_link(v, trie);
- if (trie[u].is_terminal || u == 0)
- {
- trie[v].short_link = u;
- }
- else
- {
- trie[v].short_link = get_short_link(u, trie);
- }
- }
- return trie[v].short_link;
- }
- std::tuple<int, int> build_trie(
- const size_t p_len, const std::string pattern, std::vector<vertex>& trie)
- {
- vertex buff;
- trie.push_back(buff);
- int trie_size = 1;
- int count_templates = 0;
- int start_idx = 0;
- std::string tempalate;
- size_t len_tempalate = 0;
- for (int i = 0; i < p_len; ++i)
- {
- if (pattern[i] == '?')
- {
- if (i - start_idx > 0)
- {
- len_tempalate = i - start_idx;
- tempalate = pattern.substr(start_idx, len_tempalate);
- add_string(tempalate, len_tempalate, trie, trie_size, i - 1);
- ++count_templates;
- }
- start_idx = i + 1;
- }
- }
- if (pattern[p_len - 1] != '?')
- {
- len_tempalate = p_len - start_idx;
- tempalate = pattern.substr(start_idx, len_tempalate);
- add_string(tempalate, len_tempalate, trie, trie_size, p_len - 1);
- ++count_templates;
- }
- return std::make_tuple(trie_size, count_templates);
- }
- void print_answer(const size_t p_len, const size_t t_len, const std::vector<int>& count_occurr_list,
- const int count_templates)
- {
- int count_pos = 0;
- std::vector<int> ans;
- for (int i = 0; i < t_len; ++i)
- {
- if (count_occurr_list[i] == count_templates && i + p_len <= t_len)
- {
- ++count_pos;
- ans.push_back(i);
- }
- }
- std::cout << count_pos << std::endl;
- for (int i = 0; i < count_pos; ++i)
- {
- std::cout << ans[i] << " ";
- }
- }
- std::vector<int> get_occurr_list(
- const size_t t_len, std::vector<vertex>& trie, const std::string text)
- {
- std::vector<int> count_occurr_list(t_len, 0);
- for (int v = 0, i = 0; i < t_len; ++i)
- {
- v = get_link(v, text[i], trie);
- int u = v;
- while (u > 0)
- {
- if (trie[u].is_terminal)
- {
- for (int idx = 0, k = 0; k < trie[u].entry_list.size(); ++k)
- {
- idx = i - trie[u].entry_list[k];
- if (idx >= 0 && idx < t_len)
- {
- ++count_occurr_list[idx];
- }
- }
- }
- u = get_short_link(u, trie);
- }
- }
- return count_occurr_list;
- }
- int main()
- {
- std::string pattern, text;
- std::cin >> pattern >> text;
- const size_t p_len = pattern.size();
- const size_t t_len = text.size();
- std::vector<vertex> trie;
- int trie_size, count_templates;
- std::tie(trie_size, count_templates) = build_trie(p_len, pattern, trie);
- std::vector<int> count_occurr_list = get_occurr_list(t_len, trie, text);
- print_answer(p_len, t_len, count_occurr_list, count_templates);
- return 0;
- }
Add Comment
Please, Sign In to add comment