当前位置: 代码迷 >> 综合 >> poj 4052 Hrinity AC自动机
  详细解决方案

poj 4052 Hrinity AC自动机

热度:72   发布时间:2024-01-19 05:51:48.0

题意:

给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;
}