一份好用(大雾)的Aho-Corasick自动机模板

hhw posted @ 2014年8月11日 15:25 in 代码 with tags 代码 模板 , 892 阅读

在ljoj上发现了一道AC自动机模板题,于是就学习了一下,顺便自己写了个模板,感觉工作还算正常,就是长了点,而且没有补边,不过自己用用够了

代码如下:

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct mjj{int end,son[30],dad,fail;char c;}trie[300001];
int n;
char dc[100001],wz[1000001];
int tp=1;
queue<int> q;
long long cnt=0;
void ins(int cur,int b,int e)
{
	if(b==e){trie[cur].end=1;return;}
	if(trie[cur].son[dc[b]-'a']==0)
	{
		tp++;
		trie[cur].son[dc[b]-'a']=tp;
		trie[tp].end=0;
		trie[tp].dad=cur;
		trie[tp].c=dc[b];
	}
	ins(trie[cur].son[dc[b]-'a'],b+1,e);
}
int main()
{
	int i,j,k;
	scanf("%d",&n);
	memset(trie,0,sizeof(trie));
	trie[1].end=0;
	trie[1].fail=0;
	trie[1].dad=0;
	for(i=1;i<=n;i++){scanf("%s",dc);ins(1,0,strlen(dc));}
	q.push(1);
	while(!q.empty())
	{
		for(i=0;i<='z'-'a';i++)if(trie[q.front()].son[i]!=0)
		{
			int t=trie[q.front()].son[i];
			int tt=trie[trie[t].dad].fail;
			while(tt!=0&&trie[tt].son[i]==0)tt=trie[tt].fail;
			if(tt==0)trie[t].fail=1;else trie[t].fail=trie[tt].son[i];
			q.push(t);
		}
		q.pop();
	}
	scanf("%s",wz);
	int l=strlen(wz);
	int p=1;
	for(i=0;i<l;i++)
	{
		while(p>1&&trie[p].son[wz[i]-'a']==0)p=trie[p].fail;
		if(trie[p].son[wz[i]-'a'])p=trie[p].son[wz[i]-'a'];
		int tmp=p;
		while(tmp!=1){if(trie[tmp].end==1)cnt++;tmp=trie[tmp].fail;}
	}
	printf("%d\n",cnt);
	return 0;
}
				

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter