这两道题都是AC自动机的模板题。第二题比第一题只是要多了一个出现次数，这个很简单，开个数组记录就可以了。 但是第二题有坑点。一开始我我看了HINT以为要考虑两个病毒互相包含的情况，就像这个样例：
2AABABABAABBAABABA我以为应该输出：
AABAB: 1ABA: 2然后怎么都不对。。。 后面拿别人的标程看看结果发现应该输出：
AABAB: 1ABA: 1我说这个HINT不是害人吗？ 然后改完了交上去。。。继续WA。。。 我不甘心地拿别人的标程和我自己的对拍，用的是我自己生成的随机数据，拍了1000多组都没错。我就纳闷了，结果后来看看别人的程序打的都是多组数据打法，就是一个while(scanf("%d",&n)!=EOF),然后我无语的想这题不会有多组数据吧？结果改成多组数据就AC了。我真的是无话可说。。。多组数据题目里也不讲一下。。。
代码：
//HDU2896病毒侵袭#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=505,maxm=100010;struct node{ int next[128],fail,flag;}T[maxm];int n,m,num=1,tot,que[maxm],head,tail;char ch[maxm];bool exist[maxn];void Insert(char *s,int x){ int p=1,len=strlen(s); for(int i=0;i<len;i++){ if(!T[p].next[s[i]])T[p].next[s[i]]=++num; p=T[p].next[s[i]]; } T[p].flag=x;}void Bfs(){ memset(que,head=tail=0,sizeof que); que[++tail]=1; while(head<tail){ int x=que[++head]; for(int i=0;i<128;i++){ if(T[x].next[i]){ int p=T[x].fail; while(!T[p].next[i])p=T[p].fail; T[T[x].next[i]].fail=T[p].next[i]; que[++tail]=T[x].next[i]; } } }}bool Find(char *s){ memset(exist,0,sizeof exist); int p=1,len=strlen(s);bool f=false; for(int i=0;i<len;i++){ while(p&&!T[p].next[s[i]])p=T[p].fail; p=T[p].next[s[i]]; int temp=p; while(temp&&T[temp].flag){ exist[T[temp].flag]=true; f=true; temp=T[temp].fail; } } return f;}int main(){ for(int i=0;i<128;i++){ T[0].next[i]=1; } scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("/n%s",ch); Insert(ch,i); } scanf("%d",&m);Bfs(); for(int i=1;i<=m;i++){ scanf("/n%s",ch); if(Find(ch)){ tot++; PRintf("web %d:",i); for(int i=1;i<=n;i++){ if(exist[i]){ printf(" %d",i); } } putchar(10); } } printf("total: %d/n",tot); return 0;}//HDU3065病毒侵袭持续中//多组数据！#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=2000010,maxm=50010;struct node{ int flag,next[128],fail;}T[maxm];int n,que[maxm],head,tail,num=1,ans[1010];char text[maxn],ch[1010][55];void Insert(char *s,int x){ int p=1,len=strlen(s); for(int i=0;i<len;i++){ if(!T[p].next[s[i]])T[p].next[s[i]]=++num; p=T[p].next[s[i]]; } T[p].flag=x;}void Bfs(){ memset(que,head=tail=0,sizeof que); que[++tail]=1; while(head<tail){ int x=que[++head]; for(int i=0;i<128;i++){ if(T[x].next[i]){ int p=T[x].fail; while(!T[p].next[i])p=T[p].fail; T[T[x].next[i]].fail=T[p].next[i]; que[++tail]=T[x].next[i]; } } }}void Find(char *s){ int p=1,len=strlen(s); for(int i=0;i<len;i++){ while(p&&!T[p].next[s[i]])p=T[p].fail; p=T[p].next[s[i]]; int temp=p; while(temp&&T[temp].flag){ ans[T[temp].flag]++; temp=T[temp].fail; } }}int main(){ while(scanf("%d",&n)!=EOF){ memset(T,0,sizeof T);num=1; memset(ans,0,sizeof ans); for(int i=0;i<128;i++){ T[0].next[i]=1; } for(int i=1;i<=n;i++){ scanf("/n%s",ch[i]); Insert(ch[i],i); } scanf("/n%s",text); Bfs();Find(text); for(int i=1;i<=n;i++){ if(ans[i]){ printf("%s: %d/n",ch[i],ans[i]); } } } return 0;}新闻热点
疑难解答
