[AC自动机]hdoj 3065：病毒侵袭持续中
大致题意：
? ? 给出n个模式串，一个文本串，分别求出每个文本串子在模式串中出现的次数。
?
大致思路：
? ? 基本的AC自动机，要修改一些地方。
?
#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include <algorithm>using namespace std;const int inf=1<<28;const int nMax=1500;const int mMax=2000000;class node{public: int id; int count; //前缀记录标志 node *next[30],*fail; node(){ id=-1; count=0; fail=NULL; for(int i=0;i<30;i++)next[i]=NULL; }}*root,*que[mMax];int cnt;void insert(char *s){ //构造前缀树 int i; node *r=root; int l=strlen(s); for(i=0;i<l;i++){ int loc=s[i]-'A'; if(r->next[loc]==NULL){ r->next[loc]=new node(); } r=r->next[loc]; } if(r->id==-1){ r->id=cnt; cnt++; } r->count++;}void acAuto(){ //用bfs为每个节点设定fail指针 int i,head=0,tail=0; node *p,*tmp; root->fail=NULL; que[tail++]=root; while(head<tail){ tmp=que[head++]; for(i=0;i<30;i++){ if(tmp->next[i]==NULL)continue; if(tmp==root){ tmp->next[i]->fail=root; } else { for(p=tmp->fail;p!=NULL;p=p->fail){ if(p->next[i]!=NULL){ tmp->next[i]->fail=p->next[i]; break; } } if(p==NULL){ tmp->next[i]->fail=root; } } que[tail++]=tmp->next[i]; } }}int vis[nMax];void search(char *msg){ int i,idx; node *p=root,*tmp; for(i=0;msg[i];i++){ idx=msg[i]-'A'; if(idx<0||idx>26)idx=27; while(p->next[idx]==NULL&&p!=root){ p=p->fail; } p=p->next[idx]; if(p==NULL)p=root; for(tmp=p;tmp!=NULL;tmp=tmp->fail){//&&tmp->count!=-1 因为这里需要求的是该字符串出现的次数 if(tmp->id!=-1)vis[tmp->id]++; //也就是字符需要重复出现，所以这句要注释掉 } }}char str[nMax][55],text[mMax];int main(){ int n,i,j,flag; while(scanf("%d",&n)!=EOF){ cnt=1; root=new node(); memset(vis,0,sizeof(vis)); for(i=1;i<=n;i++){ scanf("%s",str[i]); insert(str[i]); } acAuto(); scanf("%s",text); search(text); flag=1; for(i=1;i<=n;i++){ if(vis[i]!=0){ flag=0; printf("%s: %d\n",str[i],vis[i]); } } if(flag)printf("\n"); } return 0;}?