AC自動機-マルチモードストリングのマッチング運用---HDU 2896

ウイルスによる侵略
Problem's Link:http://acm.hdu.edu.cn/showproblem.php?pid=2896
 
Mean: 
 中国語の問題は解釈しません.
アナリゼ:
AC自动机の运用により、マルチモードシリアルがマッチします.いくつかの細かい点に注意しなければならないです.これらの細部に長い間カードをかけました.
1)出力されたウェブサイト番号と最終的なウイルスサイト数は同じではない.
2)nextポインタは128を設定し、そうでないとスタックが破裂します.
3)同じ理屈で、charがintに変換する場合、baseは31に設定する.
Time complexity:o(n)+o(ml) 
 
ソースコード:
 

// Memory   Time
// 1347K     0MS
// by : Snarl_jsb
// 2014-09-30-11.01
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<climits>
#include<cmath>
#define LL long long
using namespace std;


const int N = 10010;
char str[N];
struct node
{
    node *next[128];     //         128      
    node *fail;     //          
    int count;      //
    int num;
    node()      //         
    {
        for(int i = 0; i < 128; i++)
            next[i] = NULL;
        count = 0;
        fail = NULL;
        num=0;
    }
}*q[50*N];
node *root;
int head, tail;

void Insert(char *str,int num) //       .       Trie 
{
    node *p = root;
    int i = 0, index;
    while(str[i]) {
        index = str[i] - 31; //           
        if(p->next[index] == NULL) //        
            p->next[index] = new node();    //            
        p = p->next[index];     //        
        i++;
    }
    p->count++;     //                     
    p->num=num;
}
void build_ac_automation(node *root)        //      bfs  fail  
{
    root->fail = NULL;
    q[tail++] = root;
    while(head < tail) {
        node *temp = q[head++];
        node *p = NULL;
        for(int i = 0; i < 128; i++) {
            if(temp->next[i] != NULL) {
                if(temp == root) temp->next[i]->fail = root;
                else {
                    p = temp->fail;
                    while(p != NULL) {
                        if(p->next[i] != NULL) {
                            temp->next[i]->fail = p->next[i];
                            break;
                        }
                        p = p->fail;
                    }
                    if(p == NULL) temp->next[i]->fail = root;
                }
                q[tail++] = temp->next[i];
            }
        }
    }
}
int total=0;
int Query(node *root,int num)       //     +   
{
    int i = 0, cnt = 0, index;
    node *p = root;
    int idx=0;
    int ans[100];

    while(str[i])
    {
        index = str[i] - 31;
        while(p->next[index] == NULL && p != root) //      ，           count  0    ，                
            p = p->fail;//     ，p    p->fail.(   KMP next  )
        p = p->next[index];//             ，            
        if(p == NULL)
            p = root; //      ，   root，      
        node *temp = p;//
        while(temp != root && temp->count != -1)  //  --      ,  count>1，            ;           
        {
            if(temp->count>0)
            {
                cnt ++; //          
                ans[++idx]=temp->num;
            }
//            temp->count = -1;   //   -1，          cnt ，         
            temp = temp->fail;//           
        }
        i++;
    }
    if(idx==0)
        return 0;
    printf("web %d: ",num);
    sort(ans+1,ans+1+idx);
    total++;
    for(int i=1;i<idx;++i)
    {
        printf("%d ",ans[i]);
    }
    printf("%d
",ans[idx]);
    return cnt;
}

int main()
{
    int n;
    cin>>n;
    head=tail=0;
    root=new node();
    for(int i=1;i<=n;++i)
    {
        scanf("%s",str);
        Insert(str, i);
    }
    build_ac_automation(root);      //    
    int m;
    cin>>m;
    total=0;
    for(int i=1;i<=m;++i)
    {
        scanf("%s",str);
        Query(root,i);
    }
    printf("total: %d
",total);
    return 0;
}