poj 4052 Hrinity dp自动机

题意：

给n个模式串和1个主串，求他们在主串中出现的次数，子串不重复计数。

分析：

AC自动机模板题，在处理子串的时候要特殊处理，原来AC自动机是没必要写一个update_fail函数的，这已经是比较简洁的模板了。

代码：

//poj 4052
//sep9
#include <iostream>
#include <queue>
using namespace std;
struct Node
{
	int s[32],fail,fa;
	bool word,vis;
}a[200000];
bool tag[200000];
char s[5120000];
char ss[5120000];
int index;
queue<int> Q;
void  decompress()
{
	int p=0,q=0;
	while(s[p]!='\0'){
		if(s[p]>='A'&&s[p]<='Z')
			ss[q++]=s[p++];
		else{
			++p;
			int sum=0;	
			while(s[p]>='0'&&s[p]<='9'){
				sum=sum*10+(s[p]-'0');	
				++p;
			}
			char c=s[p++];
			while(sum--)
				ss[q++]=c;	
			++p;
		}
	}
	ss[q]='\0';	
}

void insert()
{
	int h=0,i=0,tmp;
	while(ss[i]!='\0'){
		int k=ss[i]-'A';
		if(!a[h].s[k])
			a[h].s[k]=++index;
		tmp=h;
		h=a[h].s[k];
		a[h].fa=tmp;
		++i;
	}	
	a[h].word=true;
}

void dfs_clear(int x)
{
	if(tag[x]==true) return;
	a[x].vis=false;	
	tag[x]=true;
	dfs_clear(a[x].fail);
	dfs_clear(a[x].fa);
}

void build_AC_Automation()
{
	while(!Q.empty()) Q.pop();
	Q.push(0);
	while(!Q.empty()){
		int h=Q.front();Q.pop();
		for(int i=0;i<26;++i)
			if(a[h].s[i]){
				Q.push(a[h].s[i]);
				if(h) a[a[h].s[i]].fail=a[a[h].fail].s[i];	
			}
			else 
				a[h].s[i]=a[a[h].fail].s[i];	
	}	
}

int main()
{
	int cases;	
	scanf("%d",&cases);
	while(cases--){
		memset(a,0,sizeof(a));	
		index=0;
		int n;
		scanf("%d",&n);
		while(n--){
			scanf("%s",s);
		 	decompress();		
			insert();
		}
		build_AC_Automation();
		scanf("%s",s);
		decompress();
		int ans=0,h=0;
		for(int i=0;ss[i]!='\0';++i){
			h=a[h].s[ss[i]-'A'];
			if(a[h].word==true)
				a[h].vis=true;
		}
		memset(tag,0,sizeof(tag));
		for(int i=0;i<=index;++i)
			if(tag[i]==false&&a[i].vis==true){
				dfs_clear(a[i].fa);
				dfs_clear(a[i].fail);	
			}
		for(int i=0;i<=index;++i)
			if(a[i].vis==true)
				++ans;
		printf("%d\n",ans);
	}
	return 0;
} 

poj 4052 Hrinity dp自动机

原文：http://blog.csdn.net/sepnine/article/details/44672667