Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- struct vertex
- {
- bool is_terminal;
- int next[26];
- int go[26];
- int parent;
- char parent_char;
- int link;
- int depth;
- int start;
- };
- void clean_trie(vertex* trie, int size)
- {
- for (int i = 0; i < size; ++i)
- {
- trie[i].is_terminal = false;
- trie[i].parent = -1;
- trie[i].link = -1;
- trie[i].depth = 0;
- for (int j = 0; j < 26; ++j)
- {
- trie[i].next[j] = -1;
- trie[i].go[j] = -1;
- }
- }
- }
- void add_string(std::string s, int s_len, vertex* trie, int& size, int start)
- {
- int v = 0;
- int c_idx;
- vertex buff;
- char c;
- for (int i = 0; i < s_len; ++i)
- {
- c = s[i];
- c_idx = static_cast<int>(c) - 97;
- if (trie[v].next[c_idx] == -1)
- {
- trie[size].link = -1;
- trie[size].parent = v;
- trie[size].parent_char = c;
- trie[v].next[c_idx] = size++;
- }
- v = trie[v].next[c_idx];
- }
- trie[v].is_terminal = true;
- trie[v].depth = s_len;
- trie[v].start = start;
- }
- int get_link(int v, char c, vertex* trie);
- int get_suff_link(int v, vertex* trie)
- {
- if (trie[v].link == -1)
- {
- 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(int v, char c, vertex* trie)
- {
- int c_idx = static_cast<int>(c) - 97;
- if (trie[v].go[c_idx] == -1)
- {
- if (trie[v].next[c_idx] != -1)
- 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];
- }
- void fill_trie(int p_len, std::string P, vertex* trie, int& trie_size, int& count)
- {
- clean_trie(trie, 26 * p_len);
- int i = 0;
- int start = 0;
- std::string mask;
- int len_mask;
- while (i < p_len)
- {
- if (P[i] == '?')
- {
- if (i - start > 0)
- {
- len_mask = i - start;
- mask = P.substr(start, len_mask);
- add_string(mask, len_mask, trie, trie_size, start);
- count++;
- }
- start = i + 1;
- }
- else if (i == p_len - 1)
- {
- len_mask = i - start + 1;
- mask = P.substr(start, len_mask);
- add_string(mask, len_mask, trie, trie_size, start);
- count++;
- }
- i++;
- }
- }
- void display(vertex* trie, int size, bool display_links)
- {
- for (int i = 0; i < size; ++i)
- {
- bool flag = true;
- for (int j = 0; j < 26; ++j)
- {
- if (trie[i].next[j] >= 0)
- {
- if (flag)
- {
- if (trie[i].is_terminal)
- std::cout << "vertex " << i << ": (is_terminal) ";
- else
- std::cout << "vertex " << i << ": ";
- flag = false;
- }
- std::cout << char(j + 97) << "->" << trie[i].next[j] << " ";
- }
- }
- if (not flag)
- std::cout << std::endl;
- if (flag && trie[i].is_terminal)
- std::cout << "vertex " << i << ": (is_terminal);" << std::endl;
- }
- if (display_links)
- {
- std::cout << "\n Ссылки:" << std::endl;
- for (int v = 0; v < size; ++v)
- {
- std::cout << "vertex: " << v << " ";
- std::cout << "suff: " << get_suff_link(v, trie) << "; ";
- std::cout << "get_link: ";
- for (int j = 0; j < 26; ++j)
- {
- int z = get_link(v, char(j + 97), trie);
- if (z > 0)
- std::cout << "(" << char(j + 97) << "," << z << ") ";
- }
- std::cout << std::endl;
- }
- }
- }
- void search_pattern(int t_len, vertex* trie, std::string T, int& count, int p_len)
- {
- if (count == 0)
- {
- count = t_len - p_len + 1;
- std::cout << count << std::endl;
- for (int i = 0; i < count; ++i)
- {
- std::cout << i << " ";
- }
- }
- else
- {
- char c;
- int v = 0;
- int u;
- int c_idx;
- int start = 0;
- int C[t_len];
- int count_pos = 0;
- for (int i = 0; i < t_len; ++i)
- C[i] = 0;
- for (int i = 0; i < t_len; ++i)
- {
- c = T[i];
- c_idx = static_cast<int>(c) - 97;
- if (trie[v].next[c_idx] == -1)
- {
- while (v > 0 && trie[v].next[c_idx] == -1)
- {
- v = get_suff_link(v, trie);
- }
- if (trie[v].next[c_idx] != -1)
- {
- v = trie[v].next[c_idx];
- }
- else
- {
- }
- }
- else
- {
- v = trie[v].next[c_idx];
- }
- if (trie[v].is_terminal)
- {
- u = v;
- while (u > 0)
- {
- if (trie[u].is_terminal)
- {
- int idx = i - trie[u].depth + 1 - trie[u].start;
- if (++C[idx] == count && (p_len + idx - 1 < t_len) && idx >= 0)
- {
- count_pos++;
- }
- }
- u = get_suff_link(u, trie);
- }
- }
- }
- std::cout << std::endl;
- std::cout << count_pos << std::endl;
- for (int i = 0; i < t_len; ++i)
- if (C[i] == count && (p_len + i - 1 < t_len))
- std::cout << i << " ";
- }
- }
- int main()
- {
- std::string P, T;
- std::cin >> P >> T;
- // P = "he?she?his?hers";
- // P = "he?she";
- // P = "abcd";
- // T = "heashe";
- //Если убрать первый ? то ошибка уходит (!)
- // P = "?a";
- // T = "aaa";
- // P = "?a";
- // T = "aaaa";
- int p_len = P.length();
- int t_len = T.length();
- int trie_size = 1;
- int max_size = 26 * p_len;
- vertex trie[max_size];
- int count = 0;
- fill_trie(p_len, P, trie, trie_size, count);
- // display(trie,max_size, false);
- search_pattern(t_len, trie, T, count, p_len);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment