首页 > 代码库 > 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;}

 注意一些细节即可