| 9 | go_node() { out = NULL; fail = NULL; } }; |
| 10 | go_node *go; |
| 11 | aho_corasick(vector<string> keywords) { |
| 12 | go = new go_node(); |
| 13 | iter(k, keywords) { |
| 14 | go_node *cur = go; |
| 15 | iter(c, *k) |
| 16 | cur = cur->next.find(*c) != cur->next.end() ? |
| 17 | cur->next[*c] : (cur->next[*c] = new go_node()); |
| 18 | cur->out = new out_node(*k, cur->out); } |
| 19 | queue<go_node*> q; |
| 20 | iter(a, go->next) q.push(a->second); |
| 21 | while (!q.empty()) { |
| 22 | go_node *r = q.front(); q.pop(); |
| 23 | iter(a, r->next) { |
| 24 | go_node *s = a->second; |
| 25 | q.push(s); |
| 26 | go_node *st = r->fail; |
| 27 | while (st && st->next.find(a->first) == |
| 28 | st->next.end()) st = st->fail; |
| 29 | if (!st) st = go; |
| 30 | s->fail = st->next[a->first]; |
| 31 | if (s->fail) { |
| 32 | if (!s->out) s->out = s->fail->out; |
| 33 | else { |
| 34 | out_node* out = s->out; |
| 35 | while (out->next) out = out->next; |
| 36 | out->next = s->fail->out; } } } } } |
| 37 | vector<string> search(string s) { |
| 38 | vector<string> res; |
| 39 | go_node *cur = go; |