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