首页 > 代码库 > AC自动机
AC自动机
没错,就是AC自动机!(可惜不像金坷垃那样~)
不多说,放上模板,不难理解的。
#include <cstdio>#include <cstring>#include <queue>#define for1(i,a,n) for(i=a;i<=n;++i)#define for2(i,a,n) for(i=a;i<n;++i)#define for3(i,a,n) for(i=n;i>=a;--i)#define for4(i,a,n) for(i=n;i>a;--i)#define CC(i,a) memset(i, a, sizeof(i))using namespace std;const int N=10000000, Type=26;char a[N], b[N];int ch[N][Type], fail[N], w[N], ans, cnt=1;queue<int> q;void ins(char* s) { int u=0, v, i, len=strlen(s); for2(i, 0, len) { v=s[i]-‘a‘; if(!ch[u][v]) ch[u][v]=cnt++; u=ch[u][v]; } w[u]++;}void bfs() { fail[0]=0; q.push(0); int u, p, i; while(!q.empty()) { u=q.front(); q.pop(); for2(i, 0, Type) if(ch[u][i]) { q.push(ch[u][i]); //先插入,后判断 if(!u) continue; //不要在这里错了。。 p=fail[u]; while(p && !ch[p][i]) p=fail[p]; fail[ch[u][i]]=ch[p][i]; } }}void ac(char* s) { int i, u=0, v, len=strlen(s), t; for2(i, 0, len) { v=s[i]-‘a‘; while(u && !ch[u][v]) u=fail[u]; u=ch[u][v]; t=u; while(t) { ans+=w[t]; w[t]=0; t=fail[t]; } }}void init() { CC(fail, 0); CC(ch, 0); CC(w, 0);}int main() { init(); scanf("%s", a); int n, i; scanf("%d", &n); for1(i, 1, n) { scanf("%s", b); ins(b); } bfs(); ac(a); printf("%d\n", ans); return 0;}
注意一些细节即可
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。