1. 首页
  2. 算法模板

AC自动机

简述

处理多模式串匹配问题,初始化后(init),先插入所有模式串(insert),然后构建AC自动机(build),最后进行匹配(next)。

假设模式串集合为 {S},目标串为 T,那么算法复杂度为 O(Simga_i |S_i| + |T|)

原理

等待填坑…

代码


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); } } } };
评分 0, 满分 5 星
0
0
看完收藏一下,下次也能找得到
0
上一篇:
:下一篇

发表评论

gravatar

沙发空缺中,还不快抢~