hdu 3065 AC 자동 동기

#include"iostream"
#include"cstdio"
#include"cstring"
#include"queue"
using namespace std;
char word[1005][55],article[2000005];
int cnt[1005];
//    
struct node
{
    int num;//   num      
    node* next[26];
    node* fail;
    node(){  //    ，     
        num=-1;
        fail=NULL;
        memset(next,NULL,sizeof(next));
    }
};
//    
void insert(int num,char* str,node* root)
{
    int i,n=strlen(str);
    node* p=root;
    for(i=0;i<n;i++){
        int k=str[i]-'A';
        if(p->next[k]==NULL){
            p->next[k]=new node();
        }
        p=p->next[k];
    }
    p->num=num;//    num      
}
//  fail  
void makeFail(node* root)
{
    queue<node*>q;
    q.push(root);
    while(!q.empty()){
        node* front=q.front();
        q.pop();
        for(int i=0;i<26;i++){
            if(front->next[i]!=NULL){
                node *temp=front->fail;
                while(temp!=NULL){
                    if(temp->next[i]!=NULL){
                        front->next[i]->fail=temp->next[i];
                        break;
                    }
                    temp=temp->fail;
                }
                if(temp==NULL)
                    front->next[i]->fail=root;
                q.push(front->next[i]);
            }
        }
    }
}
//    
void search(char* str,node* root)
{
    int i,n=strlen(str);
    node* p=root;
    for(i=0;i<n;i++){
        if(str[i]<'A'||str[i]>'Z'){//        ， root      
            p=root;
            continue;
        }
        int k=str[i]-'A';
        while(p!=root&&p->next[k]==NULL)
            p=p->fail;
        if(p->next[k]!=NULL){
            p=p->next[k];
			node* temp=p;
			while(temp!=root){
				if(temp->num!=-1) //     num       
					cnt[temp->num]++;
				temp=temp->fail;
			}
        }
    }
}
//    
void freedom(node* p)
{
    for(int i=0;i<26;i++){
        if(p->next[i]!=NULL)
            freedom(p->next[i]);
    }
    delete p;
}
//   
int main()
{
    int T,i;
    while(scanf("%d",&T)!=EOF){
        memset(cnt,0,sizeof(cnt));
        node* root=new node();
        getchar();
        for(i=0;i<T;i++){
            gets(word[i]);
            insert(i,word[i],root);
        }
        makeFail(root);
        gets(article);
        search(article,root);
        for(i=0;i<T;i++){
            if(cnt[i]>0)
                printf("%s: %d
",word[i],cnt[i]);
        }
        freedom(root);
    }
    return 0;
}