Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <unordered_map>
- #include <queue>
- using namespace std;
- struct out_node
- {
- int word_index;
- int word_len;
- out_node* next;
- out_node(int word_index, int word_len, out_node* next)
- {
- this->word_index = word_index;
- this->word_len = word_len;
- this->next = next;
- }
- };
- struct go_node
- {
- unordered_map<char, go_node*> next;
- out_node* out; go_node* fail;
- };
- struct aho_corasick
- {
- go_node* go; int n;
- aho_corasick(vector<string>& words)
- {
- n = words.size(); go = new go_node();
- for(int j=0;j<n;j++)
- {
- string word = words[j];
- go_node* c = go;
- for(int i=0;i<word.size();i++)
- {
- char ch = word[i];
- if(c->next.find(ch) != c->next.end()) c = c->next[ch];
- else
- {
- go_node* node = new go_node();
- c->next[ch] = node;
- c = node;
- }
- }
- c->out = new out_node(j, word.size(), c->out);
- }
- queue<go_node*> q;
- for(auto p: go->next) q.push(p.second);
- while(!q.empty())
- {
- go_node* r = q.front(); q.pop();
- for(auto p: r->next)
- {
- go_node* s = p.second; go_node* t = r->fail;
- q.push(s);
- while(t!=nullptr && t->next.find(p.first)==t->next.end()) t = t->fail;
- if(t==nullptr) t = go;
- s->fail = t->next[p.first];
- if(s->fail!=nullptr)
- {
- if(s->out==nullptr) s->out = s->fail->out;
- else
- {
- out_node* out = s->out;
- while(out->next!=nullptr) out = out->next;
- out->next = s->fail->out;
- }
- }
- }
- }
- }
- vector<vector<int>> search(string text)
- {
- vector<vector<int>> res(n);
- go_node* c = go;
- for(int i=0;i<text.size();i++)
- {
- char ch = text[i];
- while(c!=nullptr && c->next.find(ch)==c->next.end()) c = c->fail;
- if(c==nullptr) c = go;
- c = c->next[ch];
- if(c==nullptr) c = go;
- for(out_node* out=c->out; out!=nullptr; out=out->next) res[out->word_index].push_back(i-out->word_len+1);
- }
- return res;
- }
- };
- int main()
- {
- string text = "abccab";
- vector<string> patterns = {"a", "ab", "bc", "bab", "bca", "c", "caa"};
- aho_corasick ac(patterns);
- vector<vector<int>> res = ac.search(text);
- for(int i=0;i<res.size();i++)
- {
- cout << patterns[i] << ": \t";
- for(int j=0;j<res[i].size();j++) cout << res[i][j] << " ";
- cout << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment