Advertisement
MystMe

Untitled

Sep 18th, 2017
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.46 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3.  
  4. using namespace std;
  5.  
  6. // Структура паттерна
  7. struct Pattern{
  8.     string text;    // Текст паттерна
  9.     int size;       // Длина паттерна(количество символов в тексте)
  10.     int num;        // Номер(идентификатор) паттерна
  11.     int pos;        // Позиция паттерна в Большом Паттерне
  12.     Pattern(string t_text,const int& t_size, const int& t_num, const int& t_pos):   // Конструктор
  13.             text(std::move(t_text)),size(t_size), num(t_num), pos(t_pos) {}
  14. };
  15.  
  16. // Узел Бора(Автомата)
  17. const int alphabet_size = 255;
  18. struct Node{
  19.     vector<Node*> sons; // Указатели на всех сыновей данного узла.
  20.     vector<Node*> go;   // Массив Переходов
  21.  
  22.     Node* father;       // Отец данного узла
  23.     Node* suff;         // Суффиксная ссылка
  24.     Node* up;           // Краткая суффиксная ссылка
  25.  
  26.     char letter;        // Символ на ребре this->father ---> this
  27.     bool is_terminal;   // Является ли эта вершина терминальной(концом какого-то с лова)
  28.     vector<int> numbers_of_patters; // Номера паттернов, которые тут кончаются
  29.  
  30.     Node(){
  31.         sons.resize(alphabet_size);
  32.         for(int i = 0; i < alphabet_size; i++){
  33.             sons[i] = nullptr;
  34.         }
  35.         go.resize(alphabet_size);
  36.         for(int i = 0; i < alphabet_size; i++){
  37.             go[i] = nullptr;
  38.         }
  39.  
  40.         father = nullptr;
  41.         suff = nullptr;
  42.         up = nullptr;
  43.  
  44.         letter = '@';
  45.         is_terminal = false;
  46.     }
  47. };
  48.  
  49. // Бор(Автомат)
  50. class Bor{
  51. public:
  52.     Bor(vector<Pattern> p);  // Конструктор
  53.     ~Bor(); // Деструктор
  54.     void Transform();   // Сделать из бора автомат
  55.     vector<int> Find(string text, vector<Pattern> p);   // Найти вхождения текста
  56. private:
  57.     Node* root; // Корень
  58.  
  59.     void addLetter(string word, int pattern_number);   // Вставка буквы
  60.  
  61.     Node* getSuffLink(Node* vertex); // Получить суффиксную ссылку
  62.     Node* getLink(Node* vertex, char c);     // получить по функции перехода
  63.     Node* up(Node* vertex);      // Короткая суфф. ссылка
  64.  
  65.     void del(Node* v);
  66. };
  67. Bor::Bor(vector<Pattern> p){    // В конструктор передаем все паттерны
  68.     root = new Node;    // Корень изначально пустой
  69.  
  70.     for(auto i = p.begin(); i != p.end(); ++i){  // Добавляем в бор каждое слово-паттерн
  71.         addLetter(i->text, i->num);
  72.     }
  73. }
  74. Bor::~Bor() {
  75.     del(root);
  76. }
  77. void Bor::Transform(){
  78.     queue<Node*> q;
  79.     q.push(root);
  80.     if(root == nullptr){
  81.         return;
  82.     }
  83.     root->suff = root;
  84.     while(!q.empty()) {  // Обходом в ширину добавляем суффиксные ссылки
  85.         Node *tmp = q.front();
  86.         q.pop();
  87.         if (tmp != nullptr) {
  88.             for (int i = 0; i < tmp->sons.size(); i++) {
  89.                 if (tmp->sons[i] != nullptr) {
  90.                     q.push(tmp->sons[i]);
  91.                 }
  92.             }
  93.             if (tmp->suff == nullptr) {
  94.                 tmp->suff = getSuffLink(tmp);
  95.             }
  96.         }
  97.     }
  98. }
  99. vector<int> Bor::Find(string text, vector<Pattern> p) {
  100.     Node* current = root;
  101.     vector<int> tmp;
  102.     if(root != nullptr){
  103.         tmp.assign(text.size(),0);
  104.     }
  105.     else{
  106.         return tmp;
  107.     }
  108.     for(int pos = 0; pos < text.size(); pos++){
  109.         current = getLink(current,text[pos]);
  110.         for(auto j = 0; j < current->numbers_of_patters.size(); j++){
  111.             int pattern_num = current->numbers_of_patters[j];
  112.             int w = pos-p[pattern_num].size+1-p[pattern_num].pos;
  113.             if(w>=0){
  114.                 tmp[w]+=1;
  115.             }
  116.         }
  117.         Node* k = up(current);
  118.         while(k != root){
  119.             for(auto j = 0; j < k->numbers_of_patters.size(); j++){
  120.                 int pattern_num = k->numbers_of_patters[j];
  121.                 int w = pos-p[pattern_num].size+1-p[pattern_num].pos;
  122.                 if(w>=0){
  123.                     tmp[w]+=1;
  124.                 }
  125.             }
  126.             k = up(k);
  127.         }
  128.     }
  129.     return tmp;
  130. }
  131. void Bor::addLetter(string word, int pattern_number){
  132.     Node* cur = root;
  133.     for(auto i = 0 ; i < word.size(); i++){
  134.         char c = word[i]-'a';
  135.         if(cur->sons[c] == nullptr){
  136.             Node* tmp = new Node();
  137.             tmp->father = cur;
  138.             tmp->letter = word[i];
  139.             cur->sons[c] = tmp;
  140.         }
  141.         cur = cur->sons[c];
  142.     }
  143.     cur->is_terminal = true;
  144.     cur->numbers_of_patters.push_back(pattern_number);
  145.     return;
  146. }
  147. void Bor::del(Node* v){
  148.     if(v == nullptr){
  149.         return;
  150.     }
  151.     for(int i = 0; i < alphabet_size; ++i){
  152.         if(v->sons[i] != nullptr){
  153.             del(v->sons[i]);
  154.         }
  155.     }
  156.     delete v;
  157. }
  158. Node* Bor::getSuffLink(Node* vertex){
  159.     if(vertex == nullptr){
  160.         return nullptr;
  161.     }
  162.     if(vertex->suff == nullptr){
  163.         if((vertex == root) or (vertex->father == root)){
  164.             vertex->suff = root;
  165.         }
  166.         else{
  167.             vertex->suff = getLink(getSuffLink(vertex->father), vertex->letter);
  168.         }
  169.     }
  170.     return vertex->suff;
  171. }
  172. Node* Bor::getLink(Node* vertex, char c){
  173.     if(vertex == nullptr){
  174.         return nullptr;
  175.     }
  176.     if(vertex->go[c-'a'] == nullptr){
  177.         if(vertex->sons[c-'a'] != nullptr){
  178.             vertex->go[c-'a'] = vertex->sons[c-97];
  179.         }
  180.         else if(vertex == root){
  181.             vertex->go[c-'a'] = root;
  182.         }
  183.         else{
  184.             vertex->go[c-'a'] = getLink(getSuffLink(vertex), c);
  185.         }
  186.     }
  187.     return vertex->go[c-'a'];
  188. }
  189. Node* Bor::up(Node* vertex){
  190.     if(vertex == nullptr){
  191.         return nullptr;
  192.     }
  193.     if(vertex->up == nullptr){
  194.         if(getSuffLink(vertex)->is_terminal){
  195.             vertex->up = getSuffLink(vertex);
  196.         }
  197.         else if(getSuffLink(vertex) == root){
  198.             vertex->up = root;
  199.         }
  200.         else{
  201.             vertex->up = up(getSuffLink(vertex));
  202.         }
  203.     }
  204.     return vertex->up;
  205. }
  206. int main(){
  207.     string pattern; // Паттерн
  208.     string text;    // Текст
  209.  
  210.     cin >> pattern;
  211.     cin >> text;
  212.  
  213.     vector<Pattern> p;  // Вектор паттерна
  214.  
  215.     int num = 0;
  216.     for(int i = 0; i < pattern.size(); i++){
  217.         if(pattern[i] != '?'){
  218.             string s;
  219.             s = pattern[i];
  220.             int j = i+1;
  221.             while(pattern[j] != '?' && j < pattern.size()){
  222.                 s += pattern[j];
  223.                 j++;
  224.             }
  225.             Pattern tmp(s, s.size(), num,i);
  226.             p.push_back(tmp);
  227.             i = j-1;
  228.             num++;
  229.         }
  230.     }
  231.  
  232.     class Bor Tree(p);
  233.  
  234.     Tree.Transform();
  235.     vector<int> wer = Tree.Find(text, p);
  236.  
  237.     int num_of = p.size();
  238.     for(int i = 0; i < wer.size()-pattern.size()+1; i++){
  239.         if(wer[i] == num_of) {
  240.             if (p.size() > 0) {
  241.                 cout << i + p[0].pos << " ";
  242.             }
  243.             else{
  244.                 cout << i << " ";
  245.             }
  246.         }
  247.     }
  248.     return 0;
  249. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement