#include #include #include using namespace std; struct vertex { bool is_terminal; int next[26]; int go[26]; int parent; char parent_char; int link; int depth; vector end; int len_end; }; 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; trie[i].len_end = 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 end) { 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(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].end.push_back(end); trie[v].len_end++; } 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(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, i-1); 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, i); count++; } i++; } } 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(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 v = trie[v].next[c_idx]; u = v; while (u > 0) { if (trie[u].is_terminal) { for (int k = 0; k < trie[u].len_end; ++k) { int idx = i - trie[u].end[k]; C[idx]++; if (idx >= 0 && idx < t_len && C[idx] == count) { count_pos++; } } } u = get_suff_link(u, trie); } } 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; T = "dbaddabdbadadddbabddbddbbdaaddaddbdbdbdaddbdbdddbddddabddddadbdadddaadddbbbddbddddbbaddbdbdddddbddbabdabddadaadbdddddbabdadbbabaddbdaadddddadddbaaadbadadbadddddabddddaadbdbadaddbdaaddaddadbdbdabbdadbd"; P = "d????adbd?"; //T = "addaddadbdb"; //P = "a?a?s?a"; //T = "aaaasaasdravabssa"; int p_len = P.length(); int t_len = T.length(); //T = T.substr(161,t_len-161); //std::cout << T << endl; t_len = T.length(); int count = 0; int trie_size = 1; int max_size = 26 * p_len; vertex trie[max_size]; fill_trie(p_len, P, trie, trie_size, count); search_pattern(t_len, trie, T, count, p_len); return 0; }