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