Advertisement
Guest User

Untitled

a guest
Sep 22nd, 2019
138
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.23 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4.  
  5. int power_alph = 30;
  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(patterns_length, -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 = c + 'a';
  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.         int curVertex = 0;
  136.         for(int i = 0; i < s.length(); i++)
  137.         {
  138.             curVertex = get_link(curVertex, s[i]);
  139.             check(curVertex, i + 1);
  140.         }
  141.     }
  142.  
  143.     void answer()
  144.     {
  145.         for (int i = 0; i < _count.size(); ++i)
  146.         {
  147.             if (_count[i] == _length.size())
  148.                 std::cout << i << " ";
  149.         }
  150.     }
  151. private:
  152.     std::vector<vertex> _tree;
  153.     int _size;
  154.     std::vector<std::string> _patterns;
  155.     std::vector<int> _length;
  156.     std::vector<int> _count;
  157.     int _pat_size;
  158. };
  159.  
  160. int main() {
  161.     std::vector<std::string> patterns;
  162.     std::vector<int> length;
  163.  
  164.     std::string current_pattern;
  165.     int current_length = 0;
  166.     char c = getchar();
  167.     while(c != '\n')
  168.     {
  169.         if (c == '?')
  170.         {
  171.             if (!current_pattern.empty())
  172.             {
  173.                 patterns.push_back(current_pattern);
  174.                 length.push_back(current_length - current_pattern.size());
  175.                 current_pattern.clear();
  176.             }
  177.         }
  178.         else
  179.         {
  180.             current_pattern.push_back(c);
  181.         }
  182.         c = getchar();
  183.         current_length++;
  184.     }
  185.     if (!current_pattern.empty())
  186.     {
  187.         patterns.push_back(current_pattern);
  188.         length.push_back(current_length - current_pattern.size());
  189.     }
  190.  
  191.     std::string text;
  192.     std::cin >> text;
  193.  
  194.     Bohr borrr(patterns, length, text.size(), current_length);
  195.  
  196.     borrr.findAllPos(text);
  197.     borrr.answer();
  198.     return 0;
  199. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement