1 #include <stdio.h>
  2 #include <queue>
  3 #include <cstring>
  4 #include <algorithm>
  5 using namespace std;
  6 const int maxn = 500010;
  7 int ch[maxn][26];
  8 char str[1000010];
  9 
 10 struct ACAutomation
 11 {
 12      int ch[maxn][26],fail[maxn],val[maxn],last[maxn],sz,root;
 13 
 14      int newnode()//新建一个节点
 15      {
 16          memset(ch[sz],0,sizeof(ch[sz]));//把这个节点的26个儿子置为0
 17          val[sz]=0;//单词结尾标志
 18          return sz++;
 19      }
 20 
 21      void init()
 22      {
 23          sz=0;
 24          root = newnode();
 25      }
 26 
 27      void insert()
 28      {
 29          int len = strlen(str);
 30          int now = root;
 31          for(int i=0;i<len;i++)//对每一位进行找到对应的节点
 32          {
 33              int &tmp = ch[now][str[i]-‘a‘];//now的儿子节点str[i]是否存在
 34              if(tmp==0)
 35                 tmp=newnode();//tmp=sz;
 36              now = tmp;
 37          }
 38          val[now]++;//单词结束标记
 39      }
 40 
 41      void getfail()
 42      {
 43          queue<int> q;
 44          fail[root] = root;//根节点的失败节点为它本身
 45           for(int i = 0;i < 26;i++)
 46           {
 47                 int u = ch[root][i];
 48                 if(u!=0)//根节点的子节点的失败节点为root
 49                 {
 50                     fail[u] = last[u] = 0;
 51                     q.push(u);
 52                 }
 53           }
 54             while(!q.empty())
 55             {
 56                 int now = q.front();
 57                 q.pop();
 58                 for(int i = 0;i < 26;i++)
 59                 {
 60                     int u = ch[now][i];//当前节点A
 61                     if(!u)
 62                         ch[now][i] = ch[fail[now]][i];//fail[now]就相当于我们说的父节点的失败节点C
 63                         //当前节点now没有i这个儿子u，直接让这个点的第i个儿子u指向now的失败节点的第i个儿子
 64                     else
 65                     {
 66                         fail[u] = ch[fail[now]][i];
 67                         //如果当前节点now有i这个儿子u，那么u的失败节点显然要指向C(即fail[now])的第i个儿子
 68                         last[u] = val[fail[u]] ? fail[u]:last[fail[u]];
 69                         //沿着u的失配指针走遇到的下一个单词节点的 节点的编号。
 70                         q.push(u);
 71                     }
 72                 }
 73             }
 74 
 75         }
 76 
 77         int query()
 78         {
 79             int len = strlen(str);
 80             int now = root;
 81             int ret = 0;
 82             for(int i = 0;i < len;i++)
 83             {
 84                 now = ch[now][str[i]-‘a‘];
 85                 int tmp = now;
 86                 while(tmp != root && val[tmp])
 87                 {
 88                     ret += val[tmp];
 89                     val[tmp] = 0;
 90                     //统计完了之后，记得修改标记，以免再次统计
 91                     tmp = last[tmp];
 92                     //对于在AC自动机走过的每一个单词节点，我们都要沿着后缀链接追踪，如果后缀链接指向的点是单词节点的话，这个点一定不能忘记统计。
 93                 }
 94             }
 95             return ret;
 96         }
 97 }ac;
 98 
 99 
100 int main(){
101     int t,n;
102     scanf("%d",&t);
103     while(t--){
104         ac.init();
105         scanf("%d",&n);
106         for(int i = 0;i < n;i++){
107             scanf("%s",str);
108             ac.insert();
109         }
110         ac.getfail();
111         scanf("%s",str);
112         printf("%d\n",ac.query());
113     }
114     return 0;
115 }