vadimk772336

принята

Mar 19th, 2022 (edited)
966
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.62 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <array>
  5. #include <tuple>
  6.  
  7. namespace
  8. {
  9. constexpr int g_uninitialized = -1;
  10. constexpr int ord_shift = -97;
  11. constexpr int alphabet_size = 26;
  12. } // namespace
  13.  
  14.  
  15. struct vertex
  16. {
  17.     std::array<int, alphabet_size> next;
  18.     std::array<int, alphabet_size> go;
  19.     int parent;
  20.     char parent_char;
  21.     int link;
  22.     int short_link;
  23.     std::vector<int> entry_list;
  24.     bool is_terminal;
  25.  
  26.     vertex()
  27.     {
  28.  
  29.         for (int& edge : next)
  30.             edge = g_uninitialized;
  31.  
  32.         for (int& elem : go)
  33.             elem = g_uninitialized;
  34.  
  35.         parent = g_uninitialized;
  36.         link = g_uninitialized;
  37.         short_link = g_uninitialized;
  38.         is_terminal = false;
  39.     }
  40. };
  41.  
  42. void add_string(const std::string str, const size_t s_len, std::vector<vertex>& trie,
  43.     int& trie_size, const int entry_pos)
  44. {
  45.  
  46.     int v = 0;
  47.     for (int c_idx = 0, i = 0; i < s_len; ++i)
  48.     {
  49.         c_idx = static_cast<int>(str[i]) + ord_shift;
  50.  
  51.         if (trie[v].next[c_idx] == g_uninitialized)
  52.         {
  53.             trie[v].next[c_idx] = trie_size;
  54.             ++trie_size;
  55.  
  56.             vertex buff;
  57.             buff.parent = v;
  58.             buff.parent_char = str[i];
  59.             trie.push_back(buff);
  60.         }
  61.  
  62.         v = trie[v].next[c_idx];
  63.     }
  64.     trie[v].is_terminal = true;
  65.     trie[v].entry_list.push_back(entry_pos);
  66. }
  67.  
  68. int get_link(const int v, const char c, std::vector<vertex>& trie);
  69.  
  70. int get_suff_link(const int v, std::vector<vertex>& trie)
  71. {
  72.     if (trie[v].link == g_uninitialized)
  73.     {
  74.         if (v == 0 || trie[v].parent == 0)
  75.         {
  76.             trie[v].link = 0;
  77.         }
  78.         else
  79.         {
  80.             trie[v].link = get_link(get_suff_link(trie[v].parent, trie), trie[v].parent_char, trie);
  81.         }
  82.     }
  83.     return trie[v].link;
  84. }
  85.  
  86. int get_link(const int v, const char c, std::vector<vertex>& trie)
  87. {
  88.  
  89.     int c_idx = static_cast<int>(c) + ord_shift;
  90.  
  91.     if (trie[v].go[c_idx] == g_uninitialized)
  92.     {
  93.         if (trie[v].next[c_idx] != g_uninitialized)
  94.         {
  95.             trie[v].go[c_idx] = trie[v].next[c_idx];
  96.         }
  97.  
  98.         else if (v == 0)
  99.         {
  100.             trie[v].go[c_idx] = 0;
  101.         }
  102.  
  103.         else
  104.         {
  105.             trie[v].go[c_idx] = get_link(get_suff_link(v, trie), c, trie);
  106.         }
  107.     }
  108.  
  109.     return trie[v].go[c_idx];
  110. }
  111.  
  112. int get_short_link(const int v, std::vector<vertex>& trie)
  113. {
  114.     if (trie[v].short_link == g_uninitialized)
  115.     {
  116.         int u = get_suff_link(v, trie);
  117.         if (trie[u].is_terminal || u == 0)
  118.         {
  119.             trie[v].short_link = u;
  120.         }
  121.         else
  122.         {
  123.             trie[v].short_link = get_short_link(u, trie);
  124.         }
  125.     }
  126.  
  127.     return trie[v].short_link;
  128. }
  129.  
  130.  
  131. std::tuple<int, int> build_trie(
  132.     const size_t p_len, const std::string pattern, std::vector<vertex>& trie)
  133. {
  134.  
  135.  
  136.     vertex buff;
  137.     trie.push_back(buff);
  138.  
  139.     int trie_size = 1;
  140.     int count_templates = 0;
  141.  
  142.     int start_idx = 0;
  143.     std::string tempalate;
  144.     size_t len_tempalate = 0;
  145.     for (int i = 0; i < p_len; ++i)
  146.     {
  147.         if (pattern[i] == '?')
  148.         {
  149.             if (i - start_idx > 0)
  150.             {
  151.                 len_tempalate = i - start_idx;
  152.                 tempalate = pattern.substr(start_idx, len_tempalate);
  153.                 add_string(tempalate, len_tempalate, trie, trie_size, i - 1);
  154.                 ++count_templates;
  155.             }
  156.  
  157.             start_idx = i + 1;
  158.         }
  159.     }
  160.  
  161.     if (pattern[p_len - 1] != '?')
  162.     {
  163.         len_tempalate = p_len - start_idx;
  164.         tempalate = pattern.substr(start_idx, len_tempalate);
  165.         add_string(tempalate, len_tempalate, trie, trie_size, p_len - 1);
  166.         ++count_templates;
  167.     }
  168.  
  169.     return std::make_tuple(trie_size, count_templates);
  170. }
  171.  
  172. void print_answer(const size_t p_len, const size_t t_len, const std::vector<int>& count_occurr_list,
  173.     const int count_templates)
  174. {
  175.     int count_pos = 0;
  176.     std::vector<int> ans;
  177.     for (int i = 0; i < t_len; ++i)
  178.     {
  179.         if (count_occurr_list[i] == count_templates && i + p_len <= t_len)
  180.         {
  181.             ++count_pos;
  182.             ans.push_back(i);
  183.         }
  184.     }
  185.  
  186.     std::cout << count_pos << std::endl;
  187.     for (int i = 0; i < count_pos; ++i)
  188.     {
  189.         std::cout << ans[i] << " ";
  190.     }
  191. }
  192.  
  193. std::vector<int> get_occurr_list(
  194.     const size_t t_len, std::vector<vertex>& trie, const std::string text)
  195. {
  196.  
  197.     std::vector<int> count_occurr_list(t_len, 0);
  198.  
  199.     for (int v = 0, i = 0; i < t_len; ++i)
  200.     {
  201.         v = get_link(v, text[i], trie);
  202.  
  203.         int u = v;
  204.         while (u > 0)
  205.         {
  206.             if (trie[u].is_terminal)
  207.             {
  208.                 for (int idx = 0, k = 0; k < trie[u].entry_list.size(); ++k)
  209.                 {
  210.                     idx = i - trie[u].entry_list[k];
  211.                     if (idx >= 0 && idx < t_len)
  212.                     {
  213.                         ++count_occurr_list[idx];
  214.                     }
  215.                 }
  216.             }
  217.             u = get_short_link(u, trie);
  218.         }
  219.     }
  220.  
  221.     return count_occurr_list;
  222. }
  223.  
  224. int main()
  225. {
  226.  
  227.     std::string pattern, text;
  228.     std::cin >> pattern >> text;
  229.  
  230.     const size_t p_len = pattern.size();
  231.     const size_t t_len = text.size();
  232.  
  233.     std::vector<vertex> trie;
  234.  
  235.     int trie_size, count_templates;
  236.     std::tie(trie_size, count_templates) = build_trie(p_len, pattern, trie);
  237.  
  238.     std::vector<int> count_occurr_list = get_occurr_list(t_len, trie, text);
  239.  
  240.     print_answer(p_len, t_len, count_occurr_list, count_templates);
  241.  
  242.     return 0;
  243. }
  244.  
Add Comment
Please, Sign In to add comment