hdU 2222 Keywords Search（AC自动机）

/*
AC
AC自动机问题
参考：
http://www.cppblog.com/mythit/archive/2009/04/21/80633.html
*/

#include <iostream>
using namespace std;
const int nMax = 1000100;
const int mMax = 60;
const int Max = 26;
struct Node
{
	Node *fail;
	Node *next[Max];
	int count;
	Node()
	{
		fail = NULL;
		memset(next, 0, sizeof(next));
		count = 0;
	}
}*queue[nMax];
char keyWord[mMax];
char str[nMax];
int ans;

void insert(char s[], Node *root)
//构建tire树，这里没什么可解释，一次历遍即可
{
	Node *p = root;
	for(int i = 0; s[i]; ++ i)
	{
		int index = s[i] - 'a';
		if(p->next[index] == NULL) p->next[index] = new Node();
		p = p->next[index];
	}
	p ->count ++;
}

void buildFailNode(Node *root)
//构建失败节点，队列实现
{
	int front = 0,
		rear = 0;
	queue[front ++] = root;
	while(rear < front)
	{
		Node *p = queue[rear ++];
		for(int i = 0; i < Max; ++ i)
		{
			if(p->next[i])
			{
				Node *fa = p->fail;
				while(fa != NULL)//不断寻找p的失败节点直到发现fa子节点中也存在i节点
				{
					if(fa->next[i])
					{
						p->next[i]->fail = fa->next[i];
						break;
					}
					fa = fa->fail;
				}
				if(fa == NULL) p->next[i]->fail = root;
				queue[front ++] = p->next[i];
			}
		}
	}
}

void match(Node *root)
//寻找一串字符中，共有多少能与关键字匹配。
{
	Node *p = root;
	for(int i = 0; str[i]; ++ i)
	{
		int index = str[i] - 'a';
		while(p->next[index] == NULL && p != root)
			p = p->fail;
		p = p->next[index];
		p = (p == NULL) ? root : p;//为了配合while()中p != root的应用
		Node *_p = p;//这里需要将p另外复制给_p，p的值不能做改动,p此时存储的是第一个匹配的节点
		while(_p != root && _p->count != -1)
		//这里使用while循环即可将str[i]位置所有匹配全部找出来
		{
			ans += _p->count;
			_p->count = -1;
			_p = _p ->fail;
		}
	}
}

int main()
{
	//freopen("e://data.txt", "r", stdin);
	int T;
	scanf("%d", &T);
	while(T --)
	{
		int n;
		scanf("%d", &n);
		Node *root = new Node();
		while(n --)
		{
			scanf("%s", keyWord);
			insert(keyWord, root);
		}
		scanf("%s", str);
		buildFailNode(root);
		ans = 0;
		match(root);
		printf("%d\n", ans);
	}
	return 0;
}