学步园

   初学AC自动机，在网上查了半天资料，没看懂，最后竟还是看了一篇别人推荐的英语原文，才渐渐懂了。学习AC自动机，首先我们要有字典树和KMP的基础，字典树作为数据存储的结构基础，而KMP则为算法基础（KMP可理解为特殊的AC自动机，此时所建的字典树为一叉树）。

算法思想懂了后，就开始做这道网友极力推荐的AC自动机模板题了，哎，虽然说思想懂了，但真真实现起来也花费了差不多一天的时间。。无论如何，这都是自己做的第一道AC自动机的题目，还是勉励一下自己吧

以下是讲解AC自动机的一篇比较好的文章，虽然是英文的，但真的写得很好，强烈建议看一下

http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=1000005;
struct node
{
	int count;
	node *next[26];
	node *fail;
}memory[maxn],*root;
int cur;
node *q[maxn];

node * build_node()//添加新的节点
{
	node *p=&memory[cur];
	p->count=0;
	for(int i=0;i<26;i++)
		p->next[i]=NULL;
	cur++;
	return p;
}

void insert_tree(char *s)//添加单词到字典树中
{
	int len,index;
	node *p=root;
	len=strlen(s);
	for(int i=0;i<len;i++)
	{
		index=s[i]-'a';
		if(p->next[index]==NULL)
			p->next[index]=build_node();
		p=p->next[index];
	}
	p->count++;
}

void BFS()//建失败指针
{
	node *p,*u,*v;
	int f,r;
	root->fail=root;
	f=r=0;
	for(int i=0;i<26;i++)//先将第一层节点入栈，fail指针指向root
		if(root->next[i]!=NULL)
		{
			q[r++]=root->next[i];
			root->next[i]->fail=root;
		}
	while(f!=r)
	{
		p=q[f++];
		for(int i=0;i<26;i++)
		{
			u=p->next[i];
			if(u!=NULL)//p->u有边
			{
				q[r++]=u;//入栈
				v=p->fail;
				while(v!=root&&v->next[i]==NULL)//找最长后缀
					v=v->fail;
				u->fail=(v->next[i]==NULL)?root:v->next[i];//判断一下最长后缀是否存在
			}
		}
	}
}

int AC_AUTO(char *s)
{
	int len,ans,index;
	node *p,*tmp;
	len=strlen(s);
	p=root;
	ans=0;
	for(int i=0;i<len;i++)
	{
		index=s[i]-'a';
		while(p->next[index]==NULL&&p!=root)//若匹配失败，则找到失败指针指向的节点，直到成功匹配或到了root
			p=p->fail;
		if(p->next[index]!=NULL)
			p=p->next[index];

		//此处为找出当前状态下的所有模式串，记录并将找到的模式串标记，去重
		tmp=p;
		while(tmp!=root)
		{
			ans+=tmp->count;
			tmp->count=0;
			tmp=tmp->fail;
		}
	}
	return ans;
}

int main()
{
	int t,n;
	char word[55],text[maxn];
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		cur=0;
		root=build_node();
		while(n--)//建字典树
		{
			scanf("%s",word);
			insert_tree(word);
		}
		BFS();//初始化失败指针
		scanf("%s",text);
		printf("%d\n",AC_AUTO(text));//匹配模式串
	}
	return 0;
}