题目大意

给出一些模式串和一个被匹配串，若被匹配串包含模式串或其反转，则称该模式串感染了被匹配串。问有多少个模式串感染了被匹配串。

思路

AC自动机。用模式串去匹配被匹配串及其反转。

代码

#include<iostream>
#include<stdio.h>
using namespace std;

#define T_SIZE 5100000
#define P_SIZE 1000
#define TOTAL_P 250

struct trie
//利用结构体来封装字典树的节点。
{
	trie* next[26];
	trie* fail;
	int num;
	trie()
	//构造函数。
	{
		for(int i=0;i<26;i++)
			next[i]=NULL;
		fail=NULL;
		num=0;
	}
};

char T[T_SIZE+1];
char temp_T[T_SIZE+1];
char P[P_SIZE+1];
trie* q[TOTAL_P*P_SIZE];

void insert(trie* root,char* s)
//将字符串s所表示的单词插入到字典树中。
{
	trie* p=root;
	for(int i=0;s[i]!='\0';i++)
	{
		if(p->next[s[i]-'A']==NULL)
			p->next[s[i]-'A']=new trie;
		p=p->next[s[i]-'A'];
	}
	p->num++;
}

void  build_ac_automation(trie* root)
//利用广搜构建失败指针 
{
	int head=0,tail=0;
	q[tail++]=root;
	while(head!=tail)
	{
		trie* front=q[head++];
		//front为队头元素 
		for(int i=0;i<26;i++)
			if(front->next[i]!=NULL)
			//遍历队头元素的子节点 
			{
				trie* p=front->fail;
				while(p!=NULL)
				//只有根节点的失败指针为NULL 
				{
					if(p->next[i]!=NULL)
					//顺着失败指针往回走，直至某个节点，其拥有一个字母为'A'+i的子节点。 
					{
						front->next[i]->fail=p->next[i];
						break;
					}
					p=p->fail;
				}
				if(p==NULL)
				//p==NULL说明顺着失败指针往回走的过程中没有找到合适的节点，所以将失败指针指向根节点。 
					front->next[i]->fail=root;
				q[tail++]=front->next[i];
			}
	}
}

int ac_find(trie* root,char* T)
{
	trie* p=root;
	int sum=0;
	for(int i=0,len=strlen(T);i<len;i++)
	{
		while(p->next[T[i]-'A']==NULL&&p!=root)
		//若当前节点的没有一个字符为T[i]的儿子且当前节点不是根节点
		//通俗的讲，就是顺着失败指针往回走，直至找到合适的节点或根节点为止。 
			p=p->fail;
		if(p->next[T[i]-'A']!=NULL)
		//p->next[T[i]-'A']==NULL说明没找到合适的节点，p指针指在根节点上。
			p=p->next[T[i]-'A']; 
		trie* temp=p;
		while(temp!=root&&temp->num!=-1)
		//顺着失败指针往回走，一直到根节点。 
		{
			sum+=temp->num;
			//若当前节点的num不为0，则说明以当前节点字母结尾的单词出现过一次。
			//此单词是以上一次循环的节点单词为结尾的单词的子集。 
			temp->num=-1;
			//标记num为-1，避免重复计算。 
			temp=temp->fail;
		}
	}
	return sum;
}

void get_T(char* temp_T)
//解压母串 
{
	int len=strlen(temp_T),len_T=0;
	for(int i=0,num;i<len;i++)
		if(temp_T[i]>='A'&&temp_T[i]<='Z')
			T[len_T++]=temp_T[i];
		else if(temp_T[i]=='[')
			num=0;
		else if(temp_T[i]>='0'&&temp_T[i]<='9')
			num=(num+(temp_T[i]-'0'))*10;
		else if(temp_T[i]==']')
		{
			num/=10;
			for(int k=0;k<num-1;k++)
				T[len_T++]=temp_T[i-1];
		}
	T[len_T]='\0';
}

void reverse(char* str)
//反转字符串 
{
	int len=strlen(str);
	for(int i=0;i<len/2;i++)
		swap(str[i],str[len-i-1]);
}

int main()
{
	int t;
	for(scanf("%d",&t);t>0;t--)
	{
		trie* root=new trie;
		int n;
		scanf("%d",&n);
		getchar();
		for(int i=0;i<n;i++)
		{
			gets(P);
			insert(root,P);
		}
		build_ac_automation(root);
		gets(temp_T);
		get_T(temp_T);
		int res=0;
		res=ac_find(root,T);
		reverse(T);
		res+=ac_find(root,T);
		printf("%d\n",res);
	}
}