[AC自动机]hdoj 2896：病毒侵袭

大致题意：
? ? 给出n个模式串，m个文本串。对于每个文本串，求出哪些模式串在这个文本串中出现过。最后求出能够包含模式串的文本串总数。

?

大致思路：

? ? ac自动机模版的小小变形，要注意字符集是所有128个ASCII码可见字符。这道题用静态字典树的优化效果并不明显。

?

#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include <algorithm>using namespace std;const int inf=1<<28;const int nMax=500;const int mMax=500005;class node{public:    int id;    int vis;  //前缀记录标志    node *next[130],*fail;}*root,*que[mMax],num[500000];bool vist[mMax];int x,cnt;node *newnode(){    node * p = num + x++;    for(int i = 0; i <130; i++){        p->next[i] = NULL;    }    p->id=-1;    p->fail=NULL;    p->vis=0;    return p;}void insert(char *s){    //构造前缀树    int i;    node *r=root;    int l=strlen(s);    for(i=0;i<l;i++){        int loc=s[i];        if(r->next[loc]==NULL){            r->next[loc]=newnode();        }        r=r->next[loc];    }    if(r->id==-1)r->id=cnt++;    r->vis++;}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<130;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 search(char *msg){    int i,idx,ans=0;    node *p=root,*tmp;    for(i=0;msg[i];i++){        idx=msg[i];        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->vis!=-1           // ans+=tmp->vis;            tmp->vis=-1;            if(tmp->id!=-1){                ans=1;                vist[tmp->id]=1;            }        }    }    return ans;}int main(){    int n,m,i,sum;    char str[502],text[10002];    while(scanf("%d",&n)!=EOF){        x=0;        sum=0;        cnt=1;        root=newnode();        for(i=0;i<n;i++){            scanf("%s",str);            insert(str);        }        acAuto();        scanf("%d",&m);        for(i=1;i<=m;i++){            memset(vist,0,sizeof(vist));            scanf("%s",text);            if(search(text)!=0){                sum++;                printf("web %d:",i);                for(int j=1;j<=n;j++){                    if(vist[j]){                        printf(" %d",j);                    }                }                printf("\n");            }        }        printf("total: %d\n",sum);    }    return 0;}

?