hdu5384 Danganronpa（ac自动机+处理源字符串总容量超过二维数组容量的技巧（连接+分割））

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define LL long long
#define MAXN 2000010 
using namespace std;
char str[600010];//源串 
char p[500010];//模式串（即病毒）
struct Trie
{
	int next[500010][26];//有128个可显字符(若题目给的只有小写字母，128可能会暴),还有，注意第一个下标容量大小！！！
	//防止MLE或RE(access_violation),下面开的数组大小类似上面的数组第一个下标容量大小，
	//第一个下标表示字典树最大结点数，也就是允许的最大总的字符总数 
	int fail[500010];//失配指针  
	int end[500010];//记录数组,若要输出出现模式串的id,用end记录id
	int count[500010];//计数器 
	
	int root;//根结点指针 
	int L;//总长度
	int NewNode() //获取新结点并初始化  
	{
		for(int i=0;i<26;i++)
		{
			next[L][i]=-1;
		}
		end[L]=-1;
		count[L]=0;
		return L++;
	}
	void init() //初始化
	{
		L=0;
		root=NewNode();
	}
	void Insert(char *s,int id)
	{
		int len=strlen(s);
		int j=root;
		for(int i=0;i<len;i++)
		{
			if(next[j][s[i]-'a']==-1)//不存在该结点
			{
				next[j][s[i]-'a']=NewNode();
			}
			j=next[j][s[i]-'a'];
		}
		end[j]=id;//记录其id  
		count[j]++;
	}
	void build()
	{
		queue<int>q;
		fail[root]=root;//根结点失配指针指向自己  
		//根结点的孩子入队，其失配指针指向自己
		for(int i=0;i<26;i++)
		{
			if(next[root][i]==-1)//不存在该孩子 
			{
				next[root][i]=root;//指向自己
			}
			else
			{
				fail[next[root][i]]=root;//失配指针指向自己  
				q.push(next[root][i]); //孩子入队  
			}
		}
		int j;
		while(!q.empty())
		{
			j=q.front();
			q.pop();
			for(int i=0;i<26;i++)
			{
				if(next[j][i]==-1)//不存在该孩子，指向其父结点失配指针所指向的结点（该结点也有孩子i）  
				{
					next[j][i]=next[fail[j]][i];
				}
				else
				{
					fail[next[j][i]]=next[fail[j]][i];
					q.push(next[j][i]);
				}
			}
		}
	}
//	bool used[600010];//记录数组  
	int query(char *str,int n,int id)
	{
		int len=strlen(str);
		int j=root;
		int temp;
	//	int num[100010];num[i]表示病毒i的出现次数
	//	memset(num,0,sizeof(num));//每个病毒出现次数
		int ans1=0;//how many keywords will be match,即求目标串中出现了几个模式串（同一个模式串允许在源串的不同位置重复出现，出现一次，次数累加一次） 
		int ans2=0;//出现的模式串个数（同一个模式串不允许在源串的不同位置重复出现，即使出现多次，次数只算一次）  
	//	memset(used,false,sizeof(used));
		for(int i=0;i<len;i++)
		{
			j=next[j][str[i]-'a'];
			temp=j;
			while(temp!=root)
			{
				ans1+=count[temp];
				//count[temp]=0;模板对于这题，这句代码要注释掉才是对的，不过具体原因我暂时还不清楚，有谁知道了请告诉我一下，谢谢！
				if(end[temp]!=-1)//该单词或字符在Trie中出现了 
				{
				//	used[end[temp]]=true;//记录
					ans2++;
				//	num[end[temp]]++;
				}
				temp=fail[temp];//继续找后缀串
			}
		}
		/*if(ans2>0)//按字典序输出已出现过的模式串 
		{
		//	printf("web %d:",id);
			for(int i=1;i<=n;i++)
			{
				if(used[i])
					printf("%s: %d\n",p[i],num[i]);
			}
		}*/
		//return ans1;//返回目标串中出现的模式串个数(出现多次，次数累加算) 
		return ans1;//返回目标串中已出现过的模式串个数(出现多次，次数只算一次)
	}
};
Trie ac;
char temp[100010];
int main()
{
	//freopen("D:\in.txt","r",stdin);
    int n,m,tot,t,i,j,len,id,idx;
    scanf("%d",&t);
    while(t--)
    {
    	scanf("%d%d",&n,&m);
    	memset(str,0,sizeof(str)); //注意：这里每次都有清空，清空不能用str[0]='\0',否则WA！！！ 
    	for(i=1;i<=n;i++)
    	{	
    		scanf("%s",temp);
    		strcat(str,temp);//连接源字符串 
    		len=strlen(str);
    		str[len]=' ';
		}
    	ac.init();
    	for(i=1;i<=m;i++)
    	{
    		scanf("%s",p);
    		ac.Insert(p,i);
		}
		ac.build();
		id=1;
		idx=0;
		for(i=0;i<=len;i++)//分割源字符串 
		{
			if(str[i]==' ')
			{
				temp[idx]='\0';
				//puts(temp);
				printf("%d\n",ac.query(temp,m,id));
				id++;
				idx=0;
			}
			else
			{
				temp[idx++]=str[i];
			}
		}
	}
    return 0;
}