hdu2896 病毒侵袭 AC自动机入门题 N(N <= 500)个长度不大于200的模式串(保证所有的模式串都不相同)， M(M <= 1000)个长度不大于10000的待匹配串，问待匹配串中有哪几个模式串，

/**

题目：hdu2896 病毒侵袭

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

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

M(M <= 1000)个长度不大于10000的待匹配串，问待匹配串中有哪几个模式串，

题目保证每个待匹配串中最多有三个模式串。

思路：ac自动机做法，字符为可见字符，那么直接就是他们的ascii值作为每一个字符的标志。最多128；

由于不超过三个，所以找到3个就可以return ;节约时间。

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 = ;

vector<int> ans;

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]);

            int c = 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++){

            int c = 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]);

            if(ans.size()==) return ;

        }

    }

    void print(int j)

    {

        if(j){

            ans.push_back(val[j]);

            if(ans.size()==) return ;

            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[];

int main()

{

    int n, m;

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

    {

        ac.clear();

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

            scanf("%s",s);

            ac.insert(s,i);

        }

        ac.getFail();

        scanf("%d",&m);

        int cnt = ;

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

            ans.clear();

            scanf("%s",s);

            ac.find(s);

            if(ans.size()!=){

                cnt++;

                printf("web %d:",i);

                sort(ans.begin(),ans.end());

                for(int j = ; j < (int)ans.size(); j++){

                    printf(" %d",ans[j]);

                }

                printf("\n");

            }

        }

        printf("total: %d\n",cnt);

    }

    return ;

}

/*

3

aaa

bbb

ccc

2

aaabbbccc

bbaacc

*/