[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
",str[i],vis[i]);
            }
        }
        if(flag)printf("
");
    }
    return 0;
}