HDu 3065(acオートマトン)

ウイルス侵襲が持続中
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1707    Accepted Submission(s): 633
Problem Description
tさんはみんなが彼の前の問題を解決してくれたことに感謝しています.しかし、ウイルスの侵襲は続いている.tちゃんのたゆまぬ努力の下で、彼はネット上の「万悪の源」を発見した.これは巨大なウイルスサイトで、彼は多くのウイルスを持っていますが、このサイトに含まれているウイルスは奇妙で、これらのウイルスの特徴コードは短く、「英語の大文字」しか含まれていません.もちろんtさんは民のために害を取り除きたいと思っていますが、tさんは準備のできていない戦争をしたことがありません.自分を知って彼を知っていて、百戦危うくなくて、tはまずこのウイルスのウェブサイトの特徴を知っています:どれだけの異なるウイルスを含んで、すべてのウイルスは何回現れました.みんなはまた彼を助けることができますか?
 
Input
1行目は、ウイルス特徴コードの個数を表す整数N(1<=N<=1000)である.
次のN行は、各行がウイルス特徴コードを表し、特徴コード文字列の長さは1〜50であり、「英語大文字」のみを含む.いずれかの2つのウイルス特徴コードは、完全に同じではありません.
その後の行は、「万悪の源」サイトのソースコードを表し、ソース文字列の長さは2000000以内である.文字列の文字はすべてASCIIコードの可視文字です(リターンは含まれません).
 
Output
次の形式で行ごとに1つずつ、ウイルスの出現回数を出力します.発生していないウイルスは出力する必要はありません.
ウイルスの特徴コード:出現回数
コロンの後にスペースがあり、ウイルスフィーチャーコードの入力順に出力されます.
 
Sample Input

   
   
   
   

    
    
    
    3
AA
BB
CC
ooxxCC%dAAAoen....END
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    AA: 2
CC: 1

    
    
    
    
 
     
 
      Hint 
     
 Hit：                       。                          。             Sample   。 
    
    
    
    
     
   
   
   
   

 
なんと何度もwaが...細かいことはよく考えていません...詳しくはプログラム全体の注釈を参照してください...簡単な問題...

#include<iostream>
#include<cstdio>
#include<string>
#include<queue>
using namespace std;
#define cc(m,v) memset(m,v,sizeof(m))
#define maxN 50005
struct node{
    int fail,id,next[27];
    void init(){
        fail=-1,id=0,cc(next,0);
    }
}nod[maxN];
int p=0,vis[1005];
char as[1005][55],as2[2000005];
queue<int> que;
void buit(int v,char *s){
    int k=0,u;
    for(;*s;s++,k=nod[k].next[u])
        if(nod[k].next[u=*s-'A']==0){
            nod[k].next[u]=++p;
            nod[p].init();
        }
    nod[k].id=v;
}
void getfail(){
    int i,k,u;
    for(i=0;i<=26;i++) if(k=nod[0].next[i])
        nod[k].fail=0,que.push(k);
    while(!que.empty()){
        u=que.front(),que.pop();
        for(i=0;i<=26;i++)
            if(k=nod[u].next[i]) nod[k].fail=nod[nod[u].fail].next[i],que.push(k);
            else nod[u].next[i]=nod[nod[u].fail].next[i];
    }
}
void getans(char *s){
    cc(vis,0);
    int i,u,k=0;
    for(;*s;s++){
        if((u=(*s-'A'))<0 || u>25){k=0;continue;} //               ，  
        i=k=nod[k].next[u];
        while(i>0 && nod[i].id)
            vis[nod[i].id]++,i=nod[i].fail;
    }
}
int main(){
    int n,i;
    while(scanf("%d",&n)!=-1){
        p=0,nod[0].init();
        for(i=1;i<=n;i++){
            scanf("%s",as[i]);
            buit(i,as[i]);
        }
        getfail();
        scanf("%s",as2);
        getans(as2);
        for(i=1;i<=n;i++) if(vis[i])
            printf("%s: %d
",as[i],vis[i]);
    }
    return 0;
}