突然发现了一篇很棒的讲解ac自动机的文章https://www.cnblogs.com/nullzx/p/7499397.html，补上！～

终于get了一个新算法(｡ì _ í｡) 

自己写了一遍之后结果结果是错的，debug半天才发现有个句子放错位置了，还是不够熟悉吧555

必备算法：KMP（失配时从哪里开始匹配才是最优的）+trie（字典树建树）

ac自动机的图如下：

 具体过程我就不是很想讲了，可以看b站的视频，我觉得讲的蛮明白的：传送门

几个关键点：

  • 当前节点的fail指向的是父节点fail下面和当前节点字母相同的节点：比如长字符串是shea，当和she匹配时，因为e后面没有a，所以e这个位置匹配失败，e（最左侧的e）的fail指向的是它的父节点h（最左侧的h）的fail：h（中间的h）下面的e（中间的e），然后在这个新的e（中间的e）的基础上向下匹配，可以匹配到a
  • 节点的fail指向位置的字母和节点对应的字母相同
  • 节点e的fail指向的位置（记为e'）,e'的前缀是e前面字符串的后缀，当然也可以是空
  • 建立fail时要先从父节点的fail往下找，找不到再找父节点fail的fail
  • 在计数时每个节点都要算一下它（包括它的fail，fail的fail）的前缀是否是题里给出的单词，是的话将其标志置为-1，避免重复访问。

hdu2222ac代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
const int maxn=1e6+6;
const int maxt=5e5+5;
using namespace std;
struct node{
    int next[30];
    int fail,cnt;//cnt记录出现当前节点对应的单词的次数
}state[maxt];

queue<int> q;//存字母的编号
int size;
char s[maxn];

void init()
{
    while(!q.empty()) q.pop();
    for(int i=0;i<maxt;i++)
    {
        memset(state[i].next,0,sizeof(state[i].next));
        state[i].cnt=state[i].fail=0;
    }
    size=1;//只有根节点
}

void insert(char *s)
{
    int len=strlen(s),now=0;
    for(int i=0;i<len;i++)
    {
        int id=s[i]-'a';
        if(!state[now].next[id]) state[now].next[id]=size++;
        now=state[now].next[id];
    }
    state[now].cnt++;//单词节点
}

void build()
{
    state[0].fail=-1;//根节点
    q.push(0);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=0;i<26;i++)
        {
            int now=state[u].next[i];//当前节点的编号
            if(now)//有这个字母节点
            {
                if(u==0) state[now].fail=0;//第一层都指向根节点
                else
                {
                    int v=state[u].fail;//父节点的fail
                    while(v!=-1)
                    {
                        if(state[v].next[i])
                        {
                            state[now].fail=state[v].next[i];//指向父节点下面和当前节点字母相同的节点
                            break;
                        }
                        v=state[v].fail;//一直找，父节点fail位置的字母和父节点的字母相同
                    }
                    if(v==-1) state[now].fail=0;//没找到指向根
                }
                q.push(now);
            }
        }
    }
}

int getnum(int u)
{
    int ans=0;
    while(u)
    {
        if(state[u].cnt!=-1) ans+=state[u].cnt;
        state[u].cnt=-1;//标记，避免重复访问
        u=state[u].fail;//顺着fail那条线一直找下去，因为可能第一次fail对应的字符串（这个字符串可以不是给出的单词）的后缀可能是题里给出的单词
    }
    return ans;
}

int match(char *s)
{
    int len=strlen(s),now=0,ans=0;
    for(int i=0;i<len;i++)
    {
        int id=s[i]-'a';
        if(state[now].next[id]) now=state[now].next[id];//有当前节点继续往下找
        else//失配
        {
            int p=state[now].fail;
            while(p!=-1 && state[p].next[id]==0) p=state[p].fail;
            if(p==-1) now=0;//没找到,回到根，从根开始找s中的下一个字母
            else now=state[p].next[id];
        }
        if(state[now].cnt!=-1)//每次找到一个字母节点都要计算，这个节点可以不是单词节点
            ans+=getnum(now);
    }
    return ans;
}
//输出字典树上字母的编号和fail，检查build是否正确
/*void out()
{
    cout<<"编号："<<"fail："<<endl;
    queue<int> qq;
    qq.push(0);
    while(!qq.empty())
    {
        int x=qq.front();qq.pop();
        for(int i=0;i<26;i++)
        {
            if(state[x].next[i])
            {
                cout<<state[x].next[i]<<"    "<<state[state[x].next[i]].fail<<endl;
                qq.push(state[x].next[i]);
            }

        }
    }
}*/
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        init();
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%s",s);
            insert(s);
        }
        build();//建fail
       // out();
        scanf("%s",s);
        printf("%d\n",match(s));
    }
    return 0;
}