题目大意：给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。

输入输出格式

输入格式：

第一行一个n，表示模式串个数；

下面n行每行一个模式串；

下面一行一个文本串。

输出格式：

一个数表示答案

输入输出样例

2
a
aa
aa

2

说明

subtask1[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6,n=1；

subtask2[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6；

解题思路

AC自动机模板题，即Trie树+KMP模式匹配。

首先，将所有模式串建立到一棵Trie树，然后对文章的逐个字母进行查找。

查找主要考虑匹配失败怎么处理。跟KMP算法一样，求出最长公共前后缀，就知道失配后跳到哪个位置了。

预处理p数组（next数组），p[i]表示根结点到结点p[i]这段前缀和同等长度的以结点i结尾的后缀匹配成功（根结点无字符，默认根结点1到根结点1匹配成功）：

如果i的下一个结点匹配失败（代码28行），那么保留原来匹配过的，即p[i]之前都不需要再匹配，由于匹配失败即不存在该结点，我们可以直接修改其指针至p[i]的对应儿子，这样就可以继续、一直、“递归”找下去了；

如果i的下一个结点匹配成功（代码33行），那么i的下一个结点与p[i]的对应儿子相同就指向该儿子，不相同就“往回退”，往回退这一步在之前失配时指针已经链接好了。

需要注意的是，首字母没有公共前后缀的时候，p[i]是0，而根结点编号是1，根结点到根结点匹配成功应该链到1，故让结点0的儿子全为1。（若根结点从0编号，那么单个字符也有公共前缀了）

程序实现

代码解释：

22行之前：建立Trie树；

23行：0结点所有儿子指向1

24-36行：广搜计算next数组，失配时结点为空，广搜过程中，将next数组存入了空结点了

38-44行：匹配字符串，a的结点编号，顺着儿子往下找，找到累加单词数，找不到指针会自动往回退。