【题意】多模式串匹配母串，求模式串出现的次数。

【解题方法】AC 自动机裸题。

【AC自动机学习】 可以参考这篇blog，写得很好。点击打开链接

【AC 代码】

//
//Created By just_sort 2016/8/20
//All Rights Reserved
//
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6+10;
const int M = 5e5+10;
const int S = 26;
int n;
char s[N];
struct AcAutomata{
    int root,sz;
    int nxt[M][S],fail[M],cnt[M];
    int newnode()
    {
        cnt[sz] = 0;
        memset(nxt[sz],-1,sizeof(nxt[sz]));
        return sz++;
    }
    void init()
    {
        sz=0;
        root=newnode();
    }
    void insert(char *s)
    {
        int u = root;
        int n = strlen(s);
        for(int i=0; i<n; i++){
            int &v = nxt[u][s[i]-'a'];
            if(v==-1) v=newnode();
            u = v;
        }
        ++cnt[u];
    }
    void build()
    {
        queue<int>q;
        fail[root] = root;
        for(int i=0; i<S; i++){
            int &v = nxt[root][i];
            if(~v){
                fail[v] = root;
                q.push(v);
            }else{
                v=root;
            }
        }
        while(q.size()){
            int u = q.front();q.pop();
            for(int i=0; i<S; i++){
                int &v = nxt[u][i];
                if(~v){
                    fail[v] = nxt[fail[u]][i];
                    q.push(v);
                }else{
                    v=nxt[fail[u]][i];
                }
            }
        }
    }
    int query(char *s)
    {
        int u = root,n = strlen(s);
        int ans = 0;
        for(int i=0; i<n; i++){
            u = nxt[u][s[i]-'a'];
            for(int v=u; v!=root; v=fail[v]){
                ans += cnt[v];
                cnt[v] = 0;
            }
        }
        return ans;
    }
}ac;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        ac.init();
        for(int i=1; i<=n; i++){
            scanf("%s",s);
            ac.insert(s);
        }
        ac.build();
        scanf("%s",s);
        int ans = ac.query(s);
        printf("%d\n",ans);
    }
    return 0;
}