HDU 3065 病毒袭击持续中(AC自动机)

HDU 3065 病毒侵袭持续中(AC自动机)

模版题

trie图:

//140MS 6248K 
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define M 50050
struct node {
    node *next[26];
    node *fail;
    int id;
}trie[M],*root,*que[M];
char web[2000200];
char virus[1005][55];
int ans[1005];

struct AC{
    int head,tail,sz;
    node *createnode(){
        trie[sz].fail=NULL;
        memset(trie[sz].next,0,sizeof(trie[sz].next));
        trie[sz].id=-1;
        return &trie[sz++];
    }
    void ini(){
        sz=head=tail=0;
        root=createnode();
    }
    void Insert(char str[],int id){
        node *cur=root;
        for(int i=0;str[i];i++){
            int val=str[i]-'A';
            if(cur->next[val]==NULL){
                cur->next[val]=createnode();
            }
            cur=cur->next[val];
        }
        cur->id=id;
    }

    void acfun(){
        que[head++]=root;
        while(tail<head){
            node *cur=que[tail++];
            for(int i=0;i<26;i++){
                if(cur->next[i]!=NULL) {
                    if(cur==root) cur->next[i]->fail=root;
                    else  cur->next[i]->fail=cur->fail->next[i];
                    que[head++]=cur->next[i];
                }
                else{
                    if(cur==root) cur->next[i]=root;
                    else cur->next[i]=cur->fail->next[i];
                }
            }
        }
    }
    void query(char str[]){
        node *cur=root;
        for(int i=0;str[i];i++){
            if(str[i]<'A'||str[i]>'Z'){
                cur=root;
                continue;
            }
            int val=str[i]-'A';
            cur=cur->next[val];
            node *tmp=cur;
            while(tmp!=root){
                if(tmp->id>0) ans[tmp->id]++;
                tmp=tmp->fail;
            }
        }
    }
}ac;

int main(){
    int n;
    while(~scanf("%d",&n)){
        memset(ans,0,sizeof(ans));
        ac.ini();
        for(int i=1;i<=n;i++){
            scanf("%s",virus[i]);
            ac.Insert(virus[i],i);
        }
        ac.acfun();
        scanf("%s",web);
        ac.query(web);
        for(int i=1;i<=n;i++){
            if(ans[i]>0){
                printf("%s: %d\n",virus[i],ans[i]);
            }
        }
    }
    return 0;
}