前面已经说过kmp是一种字符串匹配算法。就是给你一个模式串p,和一个主串m。让你找出p在m中的位置；

ac自动机与kmp类似，也是一种字符串匹配算法。与kmp不同的是，kmp是单模式的字符串匹配算法。

而ac自动机是多模式的字符串匹配算法。也就是给你n个模式串p1,p2,p3.......pn，和一个主串m。,让你找出

这n个模式串在m中的位置。

有的同学可能会进行n次kmp来解决多模式字符串匹配的问题，但是这样时间复杂度太高了，所以我们考虑用ac自动机。

在讲解ac自动机之前，我必须假定你已经会字典树(如果你不会的话请自行百度)和kmp(kmp不会的可以自行百度也可以看一下

我之前写kmp讲解从动态规划角度理解kmp);

ac自动机简单来说就是在将主串m在由n个模式串建立的字典树上匹配。

但是伴随而来的问题是当匹配失败时候我们如果要重新开始匹配的话，时间复杂度仍然很高。

在这里我们回忆一下在kmp中如果我们匹配失败的时候我们还需要重新开始匹配吗？

如果你对kmp有了解的话就会知道在kmp中如果匹配失败的话，指针会指向next数组。然后继续匹配，

这样时间复杂度会大大提升。

在ac自动机也用到了类似的思想。我们建立一个失败数组。当在字典树时如果匹配失败的时候，指针就直接指向失配数

组，然后继续匹配这样就能大大提高时间复杂度了。

我们知道字典树上的每个节点都代表的一个字符串，如果给建立的字典树上每个节点都编上号的话，

那么我们假定第i个节点代表的字符串是Str[i].

那么如果由失败数组fail[i] = j，代表的是第i个节点的失败指针指向第j个节点。其中Str[j]是Str[i]的一个最大后缀。

我们用一个具体的例子来解释一下：

给你5个模式串"abcd","bcd","abefg","cd","cfg"。一个主串aecdabcdcfg;

那么我们可以建立如下字典树：

如果你对建树过程不太懂的话，建议去学习一下字典树在来看；

接下来就是对这颗树建立一个失败数组了，如图：

我们来看一下ac自动机是如何求到出fail数组的；

如果对于一个节点i，不存在一个Str[j]是Str[i]的一个最大后缀，就然fail[i]指向根节点；

如果对于一个节点i，如果存在一个Str[j]是Str[i]的一个最大后缀。假定Pi是i的父亲,Pj是j的父亲，我们只需要找到Pj就能找的

j(这点是毫无疑问的因为j总是和Pj相连)。我们仔细想一下如果Str[j]如果存在，且是Str[i]的一个最大后缀的话，那么fail[Pi]

应该指向谁？毫无疑问应该是Pj的( 即fail[Pi] = Pj );举个例子：

如上图：

大家可以看到fail[4] = 7,即str[7] 是str[4]的一个最大后缀。换成具体的字符串就是bcd是abcd的一个最大后缀。那么看他们的

父亲，bcd的父亲是bc,abcd的父亲是abc。可以看到bc仍是abc的一个最大后缀。

所以fail[Pi] = Pj是成立的。(这点和kmp求导next数组的过程很类似，可以类比着来看)；

以上就是求导fail数组的过程；

求出fail数组后就是模式串与主串匹配的过程了。

这个过程很简单，我们只需要将主串在字典树上匹配，如果能匹配就将指针指向该结点的失败指针看看能不能匹配。

(这里说明一下为什么能匹配还要将指针指向失败指针。如果能匹配只是说明主串中有一段与n个模式串的某一个前缀匹配，

可能并不是和某一模式串匹配。所以这是我们要看一下这个匹配前缀的最大后缀是不是一个模式串)；

如果不能匹配就从字典树的根节点开始重新匹配；

代码如下：

#include<stdio.h>
#include<string.h>
#include<queue>
#define mmset(a,b) memset(a,b,sizeof(a))
using namespace std;
const int INF = 1005;

/*
tire是字典树，fail是失败数组；
剩下的数组在用到的时候会说明 。
这里假定每个模式串的长度不超过45； 
*/ 
int tire[INF][30], fail[INF], End[INF],auxLen[INF]; 
char aux[INF][45] ;		 
int root = 0, index = 0;
void insert(char* data, int rt)
{
	int len = strlen(data);
	rt = root;
	for(int i = 0; i < len; i++)  //建树的过程 
	{
		int y = data[i] - 'a';
		if(tire[rt][y] == 0)
		{
			tire[rt][y] = ++index;
		}
		rt = tire[rt][y];
	}
	
	/*
	此时的rt结点是代表的字符串是该模式串，而不是模式串的一个前缀。
	在查找的时候如果End[rt]大于0,就说明rt结点代表的是一个模式串，而不是一个前缀；
	*/ 
	End[rt]++; 
	
	auxLen[rt] = len;	//把rt结点代表的字符串的长度存在auxLen中。 
	strcpy(aux[rt],data); //把rt结点代表的字符串拷贝到aux中； 
}


void build()		//通过bfs来建立失败数组 
{
	queue <int> que;
	int rt = root;
	for(int i = 0; i < 26; i++)
	{
		if(tire[rt][i] != 0)
		{
			que.push(tire[rt][i]);	//初始化，将每个模式串的的首字符加入队列 
		}
	}
	while(!que.empty())
	{
		int now = que.front();
		que.pop();
		for(int i = 0; i < 26; i++)
		{
			if(tire[now][i] == 0)
			{
				tire[now][i] = tire[fail[now]][i];
			}
			else
			{
				fail[tire[now][i]] = tire[fail[now]][i];
				que.push(tire[now][i]);
			}
		} 
	}
}
int query(char* data)   //查询过程 
{
	int len = strlen(data);
	int rt = root;
	int res = 0;
	for(int i = 0; i < len; i++)
	{
		int y = data[i] - 'a';
		rt = tire[rt][y];   
		int jump = rt;
		while(jump != root)  //如果能匹配就判断该jump结点代表的字符串是前缀还是模式串 
		{
			if(End[jump] > 0)  //如果是模式串的话 
			{
				res += End[jump] ;
				printf("%d ",i - auxLen[jump] + 2);
				printf("%s\n",aux[jump]);
				End[jump] = 0;
			} 
			/*
			将jump指向该结点的失败指针 ，
			看一下该结点代表的字符串的最大后缀是不是模式串； 
			*/ 
			jump = fail[jump];   
		}
	}
	return res;
}

/*

一组样例 
1 5
abcd
bcd
abefg
cd
bcfg
aecdabcdcfg
*/
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n;
		scanf("%d",&n);
		for(int i = 1; i <= n; i++)
		{
			char p[INF];
			scanf("%s",p);
			insert(p,root);
		}
		char m[INF];
		scanf("%s",m);
		build();
		query(m);
	}	
	return 0;
}