Advertisement
Guest User

Untitled

a guest
Sep 22nd, 2019
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.47 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4.  
  5. int power_alph = 26;
  6.  
  7. struct vertex
  8. {
  9.     std::vector<int> next; //следующие вершины
  10.     bool leaf;  //терминал ли
  11.     int p;  //вершина родитель
  12.     char pch; //значение по которому перешли
  13.     int link;   //суффиксная ссылка
  14.     int up; //сжатая суффиксная сслыка
  15.     std::vector<int> go; //массив переходов
  16.     std::vector<int> leafPatNumb;
  17.  
  18.     vertex(int patterns_length)
  19.     {
  20.         next.assign(power_alph, -1);
  21.         leaf = false;
  22.         up = link = -1;
  23.         go.assign(power_alph, -1);
  24.     }
  25. };
  26.  
  27. struct Bohr
  28. {
  29. public:
  30.     Bohr(std::vector<std::string> s, std::vector<int> l, int text_sz, int pat_size) : _patterns(std::move(s)),
  31.     _length(std::move(l)), _size(1), _pat_size(pat_size)
  32.     {
  33.         _count.assign(text_sz, 0);
  34.         _tree.emplace_back(pat_size);
  35.         _tree[0].p = _tree[0].link = _tree[0].up = 0;
  36.  
  37.         for (int i = 0; i < _patterns.size(); ++i)
  38.         {
  39.             add_string(_patterns[i], i);
  40.         }
  41.     }
  42.     void add_string(const std::string &s, int patNum)
  43.     {
  44.         int cur_vertex = 0;
  45.         for (int i = 0; i < s.size(); ++i)
  46.         {
  47.             char c = s[i] - 'a';
  48.             if (_tree[cur_vertex].next[c] == -1)
  49.             {
  50.                 _tree.emplace_back(_pat_size);
  51.                 _tree[_size].p = cur_vertex;
  52.                 _tree[_size].pch = s[i];
  53.                 _tree[cur_vertex].next[c] = _size++;
  54.             }
  55.             cur_vertex = _tree[cur_vertex].next[c];
  56.         }
  57.         _tree[cur_vertex].leaf = true;
  58.         _tree[cur_vertex].leafPatNumb.push_back(patNum);
  59.     }
  60.  
  61.     int get_suff_link(int vertex)
  62.     {
  63.         if (_tree[vertex].link == -1)
  64.         {
  65.             if (!vertex || !_tree[vertex].p)
  66.             {
  67.                 _tree[vertex].link = 0;
  68.             }
  69.             else
  70.             {
  71.                 _tree[vertex].link = get_link(get_suff_link(_tree[vertex].p), _tree[vertex].pch);
  72.             }
  73.         }
  74.         return _tree[vertex].link;
  75.     }
  76.  
  77.     int get_link(int vertex, char c)
  78.     {
  79.         if (_tree[vertex].go[c - 'a'] == -1)
  80.         {
  81.             if (_tree[vertex].next[c - 'a'] != -1)
  82.             {
  83.                 _tree[vertex].go[c - 'a'] = _tree[vertex].next[c - 'a'];
  84.             }
  85.             else if (!vertex)
  86.             {
  87.                 _tree[vertex].go[c - 'a'] = 0;
  88.             }
  89.             else
  90.             {
  91.                 _tree[vertex].go[c - 'a'] = get_link(get_suff_link(vertex), c);
  92.             }
  93.         }
  94.  
  95.         return  _tree[vertex].go[c - 'a'];
  96.     }
  97.  
  98.     int get_up(int vertex)
  99.     {
  100.         if (_tree[vertex].up == -1)
  101.         {
  102.             if (_tree[get_suff_link(vertex)].leaf)
  103.             {
  104.                 _tree[vertex].up = get_suff_link(vertex);
  105.             }
  106.             else if (!get_suff_link(vertex))
  107.             {
  108.                 _tree[vertex].up = 0;
  109.             }
  110.             else
  111.             {
  112.                 _tree[vertex].up = get_up(get_suff_link(vertex));
  113.             }
  114.         }
  115.         return _tree[vertex].up;
  116.     }
  117.  
  118.     void check(int v, int i)
  119.     {
  120.         for (int u = v; u != 0; u = get_up(u))
  121.         {
  122.             if (_tree[u].leaf)
  123.                 for (auto j : _tree[u].leafPatNumb)
  124.                 {
  125.                     //std::cout << i - _patterns[j].length() << " " << _patterns[j] << std::endl;
  126.                     int k = i - _length[j]- _patterns[j].length();
  127.                     if (k >= 0)
  128.                         _count[k]++;
  129.                 }
  130.         }
  131.     }
  132.  
  133.     void findAllPos(const std::string& s)
  134.     {
  135.         _text_size = s.size();
  136.         int curVertex = 0;
  137.         for(int i = 0; i < s.length(); i++)
  138.         {
  139.             curVertex = get_link(curVertex, s[i]);
  140.             check(curVertex, i + 1);
  141.         }
  142.     }
  143.  
  144.     void answer()
  145.     {
  146.         for (int i = 0; i < _count.size(); ++i)
  147.         {
  148.             if (_count[i] == _length.size() && _text_size - i >= _pat_size)
  149.                 std::cout << i << " ";
  150.         }
  151.     }
  152. private:
  153.     std::vector<vertex> _tree;
  154.     int _size;
  155.     std::vector<std::string> _patterns;
  156.     std::vector<int> _length;
  157.     std::vector<int> _count;
  158.     int _pat_size;
  159.     int _text_size;
  160. };
  161.  
  162. int main() {
  163.     std::ios_base::sync_with_stdio(0);
  164.     std::cin.tie(0);
  165.     std::vector<std::string> patterns;
  166.     std::vector<int> length;
  167.  
  168.     std::string current_pattern;
  169.     int current_length = 0;
  170.     //char c = getchar();
  171.     std::string pattern;
  172.     std::cin >> pattern;
  173.     for(int i = 0; i < pattern.size(); ++i)
  174.     {
  175.         if (pattern[i] == '?')
  176.         {
  177.             if (!current_pattern.empty())
  178.             {
  179.                 patterns.push_back(current_pattern);
  180.                 length.push_back(current_length - current_pattern.size());
  181.                 current_pattern.clear();
  182.             }
  183.         }
  184.         else
  185.         {
  186.             current_pattern.push_back(pattern[i]);
  187.         }
  188.         //pattern[i] = getchar();
  189.         current_length++;
  190.     }
  191.     if (!current_pattern.empty())
  192.     {
  193.         patterns.push_back(current_pattern);
  194.         length.push_back(current_length - current_pattern.size());
  195.     }
  196.  
  197.     std::string text;
  198.     std::cin >> text;
  199.  
  200.     Bohr borrr(patterns, length, text.size(), current_length);
  201.  
  202.     borrr.findAllPos(text);
  203.     borrr.answer();
  204.     return 0;
  205. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement