vadimk772336

Untitled

Mar 18th, 2022
665
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.70 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4.  
  5. struct vertex
  6. {
  7.     bool is_terminal;
  8.     int next[26];
  9.     int go[26];
  10.     int parent;
  11.     char parent_char;
  12.     int link;
  13.     int depth;
  14.     int start;
  15. };
  16.  
  17. void clean_trie(vertex* trie, int size)
  18. {
  19.     for (int i = 0; i < size; ++i)
  20.     {
  21.         trie[i].is_terminal = false;
  22.         trie[i].parent = -1;
  23.         trie[i].link = -1;
  24.         trie[i].depth = 0;
  25.         for (int j = 0; j < 26; ++j)
  26.         {
  27.             trie[i].next[j] = -1;
  28.             trie[i].go[j] = -1;
  29.         }
  30.     }
  31. }
  32.  
  33. void add_string(std::string s, int s_len, vertex* trie, int& size, int start)
  34. {
  35.  
  36.     int v = 0;
  37.     int c_idx;
  38.     vertex buff;
  39.     char c;
  40.  
  41.     for (int i = 0; i < s_len; ++i)
  42.     {
  43.         c = s[i];
  44.         c_idx = static_cast<int>(c) - 97;
  45.  
  46.         if (trie[v].next[c_idx] == -1)
  47.         {
  48.             trie[size].link = -1;
  49.             trie[size].parent = v;
  50.             trie[size].parent_char = c;
  51.             trie[v].next[c_idx] = size++;
  52.         }
  53.  
  54.         v = trie[v].next[c_idx];
  55.     }
  56.     trie[v].is_terminal = true;
  57.     trie[v].depth = s_len;
  58.     trie[v].start = start;
  59. }
  60.  
  61. int get_link(int v, char c, vertex* trie);
  62.  
  63. int get_suff_link(int v, vertex* trie)
  64. {
  65.     if (trie[v].link == -1)
  66.     {
  67.         if (v == 0 || trie[v].parent == 0)
  68.             trie[v].link = 0;
  69.         else
  70.             trie[v].link = get_link(get_suff_link(trie[v].parent, trie), trie[v].parent_char, trie);
  71.     }
  72.     return trie[v].link;
  73. }
  74.  
  75. int get_link(int v, char c, vertex* trie)
  76. {
  77.  
  78.     int c_idx = static_cast<int>(c) - 97;
  79.  
  80.     if (trie[v].go[c_idx] == -1)
  81.     {
  82.         if (trie[v].next[c_idx] != -1)
  83.             trie[v].go[c_idx] = trie[v].next[c_idx];
  84.  
  85.         else if (v == 0)
  86.             trie[v].go[c_idx] = 0;
  87.  
  88.         else
  89.             trie[v].go[c_idx] = get_link(get_suff_link(v, trie), c, trie);
  90.     }
  91.  
  92.     return trie[v].go[c_idx];
  93. }
  94.  
  95. void fill_trie(int p_len, std::string P, vertex* trie, int& trie_size, int& count)
  96. {
  97.  
  98.     clean_trie(trie, 26 * p_len);
  99.  
  100.     int i = 0;
  101.     int start = 0;
  102.     std::string mask;
  103.     int len_mask;
  104.     while (i < p_len)
  105.     {
  106.         if (P[i] == '?')
  107.         {
  108.             if (i - start > 0)
  109.             {
  110.                 len_mask = i - start;
  111.                 mask = P.substr(start, len_mask);
  112.                 add_string(mask, len_mask, trie, trie_size, start);
  113.                 count++;
  114.             }
  115.  
  116.             start = i + 1;
  117.         }
  118.  
  119.         else if (i == p_len - 1)
  120.         {
  121.             len_mask = i - start + 1;
  122.             mask = P.substr(start, len_mask);
  123.             add_string(mask, len_mask, trie, trie_size, start);
  124.             count++;
  125.         }
  126.  
  127.         i++;
  128.     }
  129. }
  130.  
  131. void display(vertex* trie, int size, bool display_links)
  132. {
  133.     for (int i = 0; i < size; ++i)
  134.     {
  135.         bool flag = true;
  136.         for (int j = 0; j < 26; ++j)
  137.         {
  138.             if (trie[i].next[j] >= 0)
  139.             {
  140.                 if (flag)
  141.                 {
  142.                     if (trie[i].is_terminal)
  143.                         std::cout << "vertex " << i << ": (is_terminal) ";
  144.                     else
  145.                         std::cout << "vertex " << i << ": ";
  146.                     flag = false;
  147.                 }
  148.                 std::cout << char(j + 97) << "->" << trie[i].next[j] << " ";
  149.             }
  150.         }
  151.         if (not flag)
  152.             std::cout << std::endl;
  153.         if (flag && trie[i].is_terminal)
  154.             std::cout << "vertex " << i << ": (is_terminal);" << std::endl;
  155.     }
  156.  
  157.     if (display_links)
  158.     {
  159.         std::cout << "\n Ссылки:" << std::endl;
  160.         for (int v = 0; v < size; ++v)
  161.         {
  162.             std::cout << "vertex: " << v << "  ";
  163.             std::cout << "suff: " << get_suff_link(v, trie) << ";  ";
  164.             std::cout << "get_link: ";
  165.             for (int j = 0; j < 26; ++j)
  166.             {
  167.                 int z = get_link(v, char(j + 97), trie);
  168.                 if (z > 0)
  169.                     std::cout << "(" << char(j + 97) << "," << z << ") ";
  170.             }
  171.             std::cout << std::endl;
  172.         }
  173.     }
  174. }
  175.  
  176. void search_pattern(int t_len, vertex* trie, std::string T, int& count, int p_len)
  177. {
  178.  
  179.  
  180.     if (count == 0)
  181.     {
  182.         count = t_len - p_len + 1;
  183.         std::cout << count << std::endl;
  184.         for (int i = 0; i < count; ++i)
  185.         {
  186.             std::cout << i << " ";
  187.         }
  188.     }
  189.  
  190.     else
  191.     {
  192.         char c;
  193.         int v = 0;
  194.         int u;
  195.         int c_idx;
  196.         int start = 0;
  197.  
  198.         int C[t_len];
  199.         int count_pos = 0;
  200.  
  201.         for (int i = 0; i < t_len; ++i)
  202.             C[i] = 0;
  203.  
  204.         for (int i = 0; i < t_len; ++i)
  205.         {
  206.  
  207.  
  208.             c = T[i];
  209.             c_idx = static_cast<int>(c) - 97;
  210.  
  211.  
  212.             if (trie[v].next[c_idx] == -1)
  213.             {
  214.                 while (v > 0 && trie[v].next[c_idx] == -1)
  215.                 {
  216.                     v = get_suff_link(v, trie);
  217.                 }
  218.  
  219.                 if (trie[v].next[c_idx] != -1)
  220.                 {
  221.                     v = trie[v].next[c_idx];
  222.                 }
  223.                 else
  224.                 {
  225.                 }
  226.             }
  227.             else
  228.             {
  229.                 v = trie[v].next[c_idx];
  230.             }
  231.  
  232.             if (trie[v].is_terminal)
  233.             {
  234.                 u = v;
  235.                 while (u > 0)
  236.                 {
  237.                     if (trie[u].is_terminal)
  238.                     {
  239.                         int idx = i - trie[u].depth + 1 - trie[u].start;
  240.                         if (++C[idx] == count && (p_len + idx - 1 < t_len) && idx >= 0)
  241.                         {
  242.                             count_pos++;
  243.                         }
  244.                     }
  245.                     u = get_suff_link(u, trie);
  246.                 }
  247.             }
  248.         }
  249.  
  250.         std::cout << std::endl;
  251.         std::cout << count_pos << std::endl;
  252.         for (int i = 0; i < t_len; ++i)
  253.             if (C[i] == count && (p_len + i - 1 < t_len))
  254.                 std::cout << i << " ";
  255.     }
  256. }
  257.  
  258. int main()
  259. {
  260.  
  261.     std::string P, T;
  262.     std::cin >> P >> T;
  263.     // P = "he?she?his?hers";
  264.     // P = "he?she";
  265.     // P = "abcd";
  266.     // T = "heashe";
  267.  
  268.     //Если убрать первый ? то ошибка уходит (!)
  269.     // P = "?a";
  270.     // T = "aaa";
  271.  
  272.     // P = "?a";
  273.     // T = "aaaa";
  274.  
  275.  
  276.     int p_len = P.length();
  277.     int t_len = T.length();
  278.  
  279.     int trie_size = 1;
  280.     int max_size = 26 * p_len;
  281.     vertex trie[max_size];
  282.     int count = 0;
  283.     fill_trie(p_len, P, trie, trie_size, count);
  284.  
  285.     // display(trie,max_size, false);
  286.  
  287.     search_pattern(t_len, trie, T, count, p_len);
  288.  
  289.  
  290.     return 0;
  291. }
  292.  
Advertisement
Add Comment
Please, Sign In to add comment