AC 自动机模版
简述
处理多模式串匹配问题，初始化后(init)，先插入所有模式串(insert)，然后构建AC自动机(build)，最后进行匹配(next)。
假设模式串集合为 ${S}$，目标串为 $T$，那么算法复杂度为 $O(Simga_i |S_i| + |T|)$。
原理
等待填坑…
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
<br />class AhoCorasiek{ protected: const static int N=2e5+50; const static int M=26; queue<int> que; int create(){ int x=++numn; memset(node[x].ch, -1, sizeof(node[x].ch)); node[x].cnt=node[x].fail=0; return x; } public: struct Node{ int ch[M]; int cnt, fail; }node[N]; int numn, rt; void init(){ numn=0, rt=create(); } void insert(char str[], int l){ int x=rt; for (int i=0; i<l; ++i){ int c=str[i]-'a'; if (node[x].ch[c]==-1) node[x].ch[c]=create(); x=node[x].ch[c]; } ++node[x].cnt; } int next(int x, int c){ while(x!=rt && node[x].ch[c]==-1) x=node[x].fail; if (node[x].ch[c]==-1) return rt; return node[x].ch[c]; } void build(){ while(!que.empty()) que.pop(); node[rt].fail=rt; for (int c=0, v; c<M; ++c){ v=node[rt].ch[c]; if (v!=-1) que.push(v), node[v].fail=rt; } while(!que.empty()){ int x=que.front(); que.pop(); node[x].cnt+=node[node[x].fail].cnt; for (int c=0, v; c<M; ++c){ v=node[x].ch[c]; if (v!=-1) que.push(v), node[v].fail=next(node[x].fail, c); } } } }; |
还没有任何评论，你来说两句吧!