AC自动机（HDU 2222: Keywords Search）

题意：

输入n个单词，再输入一篇文章，判断有多少个单词在文章中出现过

http://blog.csdn.net/niushuai666/article/details/7002823

注释都在代码里

#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
struct Trie
{
	int ans, len, x, now, root, i, loc, temp, next[500005][26], fail[500005], sum[500005];
	int Newnode()		/*申请新的节点，这个节点的位置是loc*/
	{
		for(i=0;i<=25;i++)		/*初始化当前节点*/
			next[loc][i] = -1;
		sum[loc++] = 0;				/*节点申请完毕，当前位置loc已被占用，所以让loc+1以便下次申请*/
		return loc-1;		/*返回当前节点位置*/
	}
	void Init()		/*初始化字典树*/
	{
		loc = 0;
		root = Newnode();
	}
	void Update(char a[])		/*字典树的更新*/
	{
		int len = strlen(a);
		int now = root;
		for(int i=0;i<len;i++)
		{
			x = a[i]-'a';
			if(next[now][x]==-1)			/*如果下一个字符节点不存在，建立新节点*/
				next[now][x] = Newnode();
			now = next[now][x];
		}
		sum[now]++;		/*sum[k]表示k节点是sum[k]个单词的结尾*/
	}
	void Create()
	{
		queue<int> q;				/*fail[k]的作用：文章如果在k节点匹配失败，则可以跳到fail[k]处继续匹配，这个同理KMP的next[]数组*/
		fail[root] = root;
		for(i=0;i<=25;i++)
		{
			if(next[root][i]==-1)
				next[root][i] = root;
			else
			{
				fail[next[root][i]] = root;				/*初始化根节点与它的所有子节点的失败指针*/
				q.push(next[root][i]);			/*根节点与它的所有子节点（位置loc）进入队列*/
			}
		}
		while(q.empty()==0)			/*从字典树的根开始进行广搜*/
		{
			now = q.front();
			q.pop();
			for(i=0;i<=25;i++)
			{
				if(next[now][i]==-1)				/*k节点的某个子节点不存在，那么可以跳到fail[k]对应的子节点*/
					next[now][i] = next[fail[now]][i];
				else
				{
					fail[next[now][i]] = next[fail[now]][i];	/*k节点的某个子节点p存在，那么fail[p]就是fail[k]对应相同字符的子节点*/
					q.push(next[now][i]);
				}
			}
		}
	}
	int Query(char a[])
	{
		ans = 0;
		len = strlen(a);
		now = root;
		for(i=0;i<len;i++)
		{
			now = next[now][a[i]-'a'];
			temp = now;
			while(temp!=root)			/*可能多个节点满足匹配条件，即某个单词后缀为另一个单词的前缀（awigknm的m所在节点可以跳到gknm的m所在节点）*/
			{												/*↑↑↑KMP的套路↑↑↑*/
				ans += sum[temp];
				sum[temp] = 0;					/* 文章中出现同样的单词只会被算作一次*/
				temp = fail[temp];
			}
		}
		return ans;
	}
};
char str[1000005];
Trie AC;
int main(void)
{
	int T, i, n;
	scanf("%d", &T);
	while(T--)
	{
		AC.Init();
		scanf("%d", &n);
		for(i=1;i<=n;i++)
		{
			scanf("%s", str);
			AC.Update(str);
		}
		AC.Create();
		scanf("%s", str);
		printf("%d\n", AC.Query(str));
	}
	return 0;
}