matbensch

Aho Corasick C++

Nov 14th, 2023
787
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.92 KB | None | 0 0
  1. #include <iostream>
  2. #include <unordered_map>
  3. #include <queue>
  4.  
  5. using namespace std;
  6.  
  7. struct out_node
  8. {
  9.     int word_index;
  10.     int word_len;
  11.     out_node* next;
  12.    
  13.     out_node(int word_index, int word_len, out_node* next)
  14.     {
  15.         this->word_index = word_index;
  16.         this->word_len = word_len;
  17.         this->next = next;
  18.     }
  19. };
  20.  
  21. struct go_node
  22. {
  23.     unordered_map<char, go_node*> next;
  24.     out_node* out; go_node* fail;
  25. };
  26.  
  27. struct aho_corasick
  28. {
  29.     go_node* go; int n;
  30.    
  31.     aho_corasick(vector<string>& words)
  32.     {
  33.         n = words.size(); go = new go_node();
  34.         for(int j=0;j<n;j++)
  35.         {
  36.             string word = words[j];
  37.             go_node* c = go;
  38.             for(int i=0;i<word.size();i++)
  39.             {
  40.                 char ch = word[i];
  41.                 if(c->next.find(ch) != c->next.end()) c = c->next[ch];
  42.                 else
  43.                 {
  44.                     go_node* node = new go_node();
  45.                     c->next[ch] = node;
  46.                     c = node;
  47.                 }
  48.             }
  49.             c->out = new out_node(j, word.size(), c->out);
  50.         }
  51.  
  52.         queue<go_node*> q;
  53.         for(auto p: go->next) q.push(p.second);
  54.         while(!q.empty())
  55.         {
  56.             go_node* r = q.front(); q.pop();
  57.             for(auto p: r->next)
  58.             {
  59.                 go_node* s = p.second; go_node* t = r->fail;
  60.                 q.push(s);
  61.                 while(t!=nullptr && t->next.find(p.first)==t->next.end()) t = t->fail;
  62.                 if(t==nullptr) t = go;
  63.  
  64.                 s->fail = t->next[p.first];
  65.                 if(s->fail!=nullptr)
  66.                 {
  67.                     if(s->out==nullptr) s->out = s->fail->out;
  68.                     else
  69.                     {
  70.                         out_node* out = s->out;
  71.                         while(out->next!=nullptr) out = out->next;
  72.                         out->next = s->fail->out;
  73.                     }
  74.                 }
  75.             }
  76.         }
  77.  
  78.     }
  79.  
  80.     vector<vector<int>> search(string text)
  81.     {
  82.         vector<vector<int>> res(n);
  83.  
  84.         go_node* c = go;
  85.         for(int i=0;i<text.size();i++)
  86.         {
  87.             char ch = text[i];
  88.             while(c!=nullptr && c->next.find(ch)==c->next.end()) c = c->fail;
  89.             if(c==nullptr) c = go;
  90.             c = c->next[ch];
  91.             if(c==nullptr) c = go;
  92.  
  93.             for(out_node* out=c->out; out!=nullptr; out=out->next) res[out->word_index].push_back(i-out->word_len+1);
  94.         }
  95.  
  96.         return res;
  97.     }
  98.  
  99. };
  100.  
  101. int main()
  102. {
  103.     string text = "abccab";
  104.     vector<string> patterns = {"a", "ab", "bc", "bab", "bca", "c", "caa"};
  105.  
  106.     aho_corasick ac(patterns);
  107.     vector<vector<int>> res = ac.search(text);
  108.     for(int i=0;i<res.size();i++)
  109.     {
  110.         cout << patterns[i] << ": \t";
  111.         for(int j=0;j<res[i].size();j++) cout << res[i][j] << " ";
  112.         cout << '\n';
  113.     }
  114. }
Advertisement
Add Comment
Please, Sign In to add comment