1 #include <stdio.h>  
  2 #include <stdlib.h>  
  3 #include <string.h>  
  4 struct Node
  5 {
  6     int cnt;//是否为该单词的最后一个结点   
  7     Node *fail;//失败指针   
  8     Node *next[26];//Trie中每个结点的各个节点   
  9 }*queue[500005];//队列，方便用BFS构造失败指针   
 10 char s[1000005];//主字符串   
 11 char keyword[55];//需要查找的单词   
 12 Node *root;//头结点   
 13 void Init(Node *root)//每个结点的初始化   
 14 {
 15     root->cnt = 0;
 16     root->fail = NULL;
 17     for (int i = 0; i<26; i++)
 18         root->next[i] = NULL;
 19 }
 20 
 21 void Build_trie(char *keyword)//构建Trie树   
 22 {
 23     Node *p, *q;
 24     int i, v;
 25     int len = strlen(keyword);
 26     for (i = 0, p = root; i<len; i++)
 27     {
 28         v = keyword[i] - 'a';
 29         if (p->next[v] == NULL)
 30         {
 31             q = (struct Node *)malloc(sizeof(Node));
 32             Init(q);
 33             p->next[v] = q;//结点链接   
 34         }
 35         p = p->next[v];//指针移动到下一个结点   
 36     }
 37     p->cnt++;//单词最后一个结点cnt++，代表一个单词   
 38 }
 39 
 40 void Build_AC_automation(Node *root)
 41 {
 42     int head = 0, tail = 0;//队列头、尾指针   
 43     queue[head++] = root;//先将root入队   
 44     while (head != tail)
 45     {
 46         Node *p = NULL;
 47         Node *temp = queue[tail++];//弹出队头结点   
 48         for (int i = 0; i<26; i++)
 49         {
 50             if (temp->next[i] != NULL)//找到实际存在的字符结点   
 51             { //temp->next[i] 为该结点，temp为其父结点   
 52                 if (temp == root)//若是第一层中的字符结点，则把该结点的失败指针指向root   
 53                     temp->next[i]->fail = root;
 54                 else
 55                 {
 56                     //依次回溯该节点的父节点的失败指针直到某节点的next[i]与该节点相同，  
 57                     //则把该节点的失败指针指向该next[i]节点；   
 58                     //若回溯到 root 都没有找到，则该节点的失败指针指向 root  
 59                     p = temp->fail;//将该结点的父结点的失败指针给p   
 60                     while (p != NULL)
 61                     {
 62                         if (p->next[i] != NULL)
 63                         {
 64                             temp->next[i]->fail = p->next[i];
 65                             break;
 66                         }
 67                         p = p->fail;
 68                     }
 69                     //让该结点的失败指针也指向root   
 70                     if (p == NULL)
 71                         temp->next[i]->fail = root;
 72                 }
 73                 queue[head++] = temp->next[i];//每处理一个结点，都让该结点的所有孩子依次入队   
 74             }
 75         }
 76     }
 77 }
 78 int query(Node *root)
 79 { //i为主串指针，p为模式串指针   
 80     int i, v, count = 0;
 81     Node *p = root;
 82     int len = strlen(s);
 83     for (i = 0; i<len; i++)
 84     {
 85         v = s[i] - 'a';
 86         //由失败指针回溯查找，判断s[i]是否存在于Trie树中   
 87         while (p->next[v] == NULL && p != root)
 88             p = p->fail;
 89         p = p->next[v];//找到后p指针指向该结点   
 90         if (p == NULL)//若指针返回为空，则没有找到与之匹配的字符   
 91             p = root;
 92         Node *temp = p;//匹配该结点后，沿其失败指针回溯，判断其它结点是否匹配   
 93         while (temp != root)//匹配结束控制   
 94         {
 95             if (temp->cnt >= 0)//判断该结点是否被访问   
 96             {
 97                 count += temp->cnt;//由于cnt初始化为 0，所以只有cnt>0时才统计了单词的个数   
 98                 temp->cnt = -1;//标记已访问过   
 99             }
100             else//结点已访问，退出循环   
101                 break;
102             temp = temp->fail;//回溯 失败指针 继续寻找下一个满足条件的结点   
103         }
104     }
105     return count;
106 }
107 
108 int main()
109 {
110     int T, n;
111     scanf("%d", &T);
112     while (T--)
113     {
114         root = (struct Node *)malloc(sizeof(Node));
115         Init(root);
116         scanf("%d", &n);
117         for (int i = 0; i<n; i++)
118         {
119             scanf("
%s", keyword);
120             Build_trie(keyword);
121         }
122         Build_AC_automation(root);
123         scanf("
%s", s);
124         printf("%d
", query(root));
125     }
126     return 0;
127 }