hdu3065 病毒侵袭持续中 AC自动机入门题 N(N <= 1000)个长度不大于50的模式串(保证所有的模式串都不相同)， 一个长度不大于2000000的待匹配串，求模式串在待匹配串中的出现次数。

/**

题目：hdu3065 病毒侵袭持续中

链接：http://acm.hdu.edu.cn/showproblem.php?pid=3065

题意：N(N <= 1000)个长度不大于50的模式串(保证所有的模式串都不相同)，

一个长度不大于2000000的待匹配串，求模式串在待匹配串中的出现次数。

思路：ac自动机做发，val标记每一个病毒串编号，通过print函数统计每一个病毒出现的次数。

AC自动机好文章：http://www.cppblog.com/menjitianya/archive/2014/07/10/207604.html

*/

#include<bits/stdc++.h>

using namespace std;

#define P pair<int,int>

#define ms(x,y) memset(x,y,sizeof x)

#define LL long long

const int maxn = ;

const int mod = 1e9+;

const int maxnode = *+;

const int sigma_size = ;

int cnt[];

struct AhoCorasickAutomata

{

    int ch[maxnode][sigma_size];

    int val[maxnode];

    int sz;

    int f[maxnode];

    int last[maxnode];

    void clear(){sz = ; memset(ch[],,sizeof ch[]); }

    int idx(char c){return c-'A'; }

    void insert(char *s,int x)

    {

        int u = , n = strlen(s);

        for(int i = ; i < n; i++){

            int c = idx(s[i]);

            if(!ch[u][c]){

                memset(ch[sz], , sizeof ch[sz]);

                val[sz] = ;

                ch[u][c] = sz++;

            }

            u = ch[u][c];

        }

        val[u] = x;

    }

    void find(char *T){

        int n = strlen(T);

        int j = ;

        for(int i = ; i < n; i++){

            if(T[i]>'Z'||T[i]<'A'){

                j = ; continue;

            }

            int c = idx(T[i]);

            //while(j&&!ch[j][c]) j = f[j];

            j = ch[j][c];

            if(val[j]) print(j);

            else if(last[j]) print(last[j]);

        }

    }

    void print(int j)

    {

        if(j){

            cnt[val[j]]++;

            print(last[j]);

        }

    }

    void getFail(){

        queue<int> q;

        f[] = ;

        for(int c = ; c < sigma_size; c++){

            int u = ch[][c];

            if(u){f[u] = ; q.push(u); last[u] = ;}

        }

        while(!q.empty()){

            int r = q.front(); q.pop();

            for(int c = ; c < sigma_size; c++){

                int u = ch[r][c];

                if(!u){

                    ch[r][c] = ch[f[r]][c]; continue;

                }//if(!u) continue;

                q.push(u);

                int v = f[r];

                while(v&&!ch[v][c]) v = f[v];

                f[u] = ch[v][c];

                last[u] = val[f[u]] ? f[u] : last[f[u]];

            }

        }

    }

} ac ;

char s[];

char t[][];

int main()

{

    int n, m;

    while(scanf("%d",&n)==)

    {

        ac.clear();

        ms(cnt,);

        for(int i = ; i <= n; i++){

            scanf("%s",t[i]);

            ac.insert(t[i],i);

        }

        ac.getFail();

        scanf("%s",s);

        ac.find(s);

        for(int i = ; i <= n; i++){

            if(cnt[i]){

                printf("%s: %d\n",t[i],cnt[i]);

            }

        }

    }

    return ;

}

/*

3

AA

BB

CC

ooxxCC%dAAAoen....END

*/