hdu 2222 Keywords Search ac自动机入门

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2222

题意:有N(N <= 10000)个长度不超过50的模式串和一个长度不超过1e6的文本串。其中模式串可以重复。问有多少文本串在模式串中出现过。(对于相同的模式串次数仍然累加)

思路:ac自动机裸题；

KMP是先将文本串进行匹配得到失配边f[];但是并不适用于文本串较长，模式串较多的情况。因为每次查询的时间复杂度为O(n+m).n,m分别为文本串和模式串的长度；

ac自动机就是建立在Trie上，用bfs得到适配边的一个逆向过程；

即将所有的模式串建立一个状态转移，之后直接匹配文本串即可；

关键:每次看的是文本串中的当前点的后缀是那个模式串的前缀，(BFS中获得f[]的关键思想)或者就是那个模式串。之后递归打印即可；

// 358MS 32704K
#include<iostream>

#include<cstdio>

#include<cstring>

#include<string.h>

#include<algorithm>

#include<vector>

#include<cmath>

#include<stdlib.h>

#include<time.h>

#include<stack>

#include<set>

#include<map>

#include<queue>

using namespace std;

#define rep0(i,l,r) for(int i = (l);i < (r);i++)

#define rep1(i,l,r) for(int i = (l);i <= (r);i++)

#define rep_0(i,r,l) for(int i = (r);i > (l);i--)

#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)

#define MS0(a) memset(a,0,sizeof(a))

#define MS1(a) memset(a,-1,sizeof(a))

#define MSi(a) memset(a,0x3f,sizeof(a))

#define inf 0x3f3f3f3f

#define lson l, m, rt << 1

#define rson m+1, r, rt << 1|1

typedef pair<int,int> PII;

#define A first

#define B second

#define MK make_pair

typedef __int64 ll;

template<typename T>

void read1(T &m)

{

    T x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    m = x*f;

}

template<typename T>

void read2(T &a,T &b){read1(a);read1(b);}

template<typename T>

void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}

template<typename T>

void out(T a)

{

    if(a>) out(a/);

    putchar(a%+'');

}

int T,kase = ,i,j,k,n,m;

const int sigma_size = ;

const int maxn = *+;

struct Aho_Corasick{

    int ch[maxn][sigma_size];

    int val[maxn],f[maxn],last[maxn],cnt[maxn];

    int sz;

    map<string,int> ms;

    Aho_Corasick(){}

    void init(){sz = ; MS0(ch[]);MS0(cnt);ms.clear();}

    void Insert(char *s,int v){

        int u = ,n = strlen(s);

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

            int c = s[i] -'a';

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

                MS0(ch[sz]);

                val[sz] = ;

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

            }

            u = ch[u][c];

        }

        val[u] = v;

        ms[string(s)] = v;//使用map来对应重复出现的字符串;竟然可以强转..

    }

    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;}//实现压缩

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

            }

        }

    }

    //从文本串中找模板;

    void Find(char *T){

        int n = strlen(T);

        int j = ;

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

            int c = T[i] - 'a';

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

        }

    }

}ac;

char p[][];

char text[];

int main()

{

    read1(T);

    while(T--){

        ac.init();

        read1(n);

        rep1(i,,n){

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

            ac.Insert(p[i],i);

        }

        ac.getFail();

        scanf("%s",text);

        ac.Find(text);

        int ans = ;

        rep1(i,,n){

            if(ac.cnt[ac.ms[string(p[i])]]) ans++;

        }

        out(ans);

        puts("");

    }

    return ;

}