hdu 3065ウイルス侵襲が継続中(AC atomaton)

タイトル:http://acm.hdu.edu.cn/showproblem.php?pid=3065
各サブストリングは違っています.ソースストリングの中で各サブストリングの出現回数を求めて、入力順に0より大きい出力が出ます.たとえば:
Sample Input

   
   
   
   

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

 
Sample Output

   
   
   
   

    
    
    
    AA: 2
CC: 1

    
    
    
    
 
     
 
      Hint 
     
 Hit：                       。                          。             Sample   。 
    
    
    
    
     
   
   
   
   

AC自動动机テンプレートのinsert関数コードp->sum+;統計的には、サブストリングの出現回数(同じサブストリングができる可能性があります.その時はsumが1より大きいです.)です.本題のサブストリングは一回だけ現れます.ソースストリングの中で各サブストリングの出現回数を見つけて、対応するサブストリングを出力します.文字列と結点のマッピング関係を作成します.出力のsumも柔軟に処理します.実際には、タグはソースコードを決定していますが、重複することができますか?マークは重複してはいけません.マークがないと重複することができます.ところで、AC自动机はメモリを消费するアルゴリズムを见たことがあります.提出するたびにメモリ制限と密接な接触があります.

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int head,tail;
const int nn=60; //122-65=57
int N;
char str[2000010],keyword[55];  
char s[1000][55];
struct node{
    int sum,id;
    node *next[nn],*fail;
    bool operator <(const node other)const {
        return id>other.id;
    }
    node(){ //inital node
        fail=NULL;
        id=sum=0;
        memset(next,0,sizeof(next)); //here
    }
}*q[55*1000];
node *root;
void insert_t(char str[],int dex){
    int temp,len;
    node *p=root;
    len=strlen(str);
    for(int i=0;i<len;i++){
        temp=str[i]-65;
        if(p->next[temp]==NULL)p->next[temp]=new node();
        p=p->next[temp];
    }
    p->id=dex;
    strcpy(s[dex],str);
    p->sum++;
}
void build_ac(){  //inital fail point
    q[tail++]=root;
    while(head<tail){
        node *p=q[head++],*temp=NULL;
        for(int i=0;i<nn;i++){
            if(p->next[i]!=NULL){
                if(p==root)p->next[i]->fail=root;
                else {
                temp=p->fail;
                while(temp){
                    if(temp->next[i]){
                        p->next[i]->fail=temp->next[i];
                        break;
                    }
                    temp=temp->fail;
                }
                if(!temp)p->next[i]->fail=root;
                }
                q[tail++]=p->next[i];
            }
        }
    }
}
priority_queue<node> que;
void query(){  
    int i,dex,len=strlen(str);
    node *p=root;
    for(i=0;i<len;i++){
        dex=str[i]-65;
        if(dex<0||dex>57){
            p=root;
            continue;
        }
        while(p->next[dex]==NULL&&p!=root)p=p->fail;
        p=p->next[dex];
        if(!p)p=root;
        node *temp=p;
        while(temp!=root&&temp->sum!=0){
            que.push(*temp);
            temp=temp->fail;
        }
    }
}
int main()
{
    int t;
    while(cin>>N){
        head=tail=0;
        root=new node();
        int i,j,total=0;
        for(i=0;i<N;i++){
            scanf("%s",keyword);
            insert_t(keyword,i+1);
        }
        build_ac();
        scanf("%s",str);
        query();
        while(!que.empty()){
            node temp1=que.top();
            que.pop();
            if(!que.empty()){
                node temp2=que.top();
                //que.pop();
                while(temp1.id==temp2.id){
                    temp2.sum+=temp1.sum;  //  sum
                    temp1=temp2;
                    que.pop();
                    if(!que.empty()){
                        temp2=que.top();
                    }
                    else break;
                }
            }
            printf("%s: %d
",s[temp1.id],temp1.sum);
        }
    }
    return 0;
}