给定 个长度不超过 的由小写英文字母组成的单词，以及一篇长为 的文章。
请问，其中有多少个单词在文章中出现了。
注意：每个单词不论在文章中出现多少次，仅累计 次。
输入格式
第一行包含整数 ，表示共有 组测试数据。
对于每组数据，第一行一个整数 ，接下去 行表示 个单词，最后一行输入一个字符串，表示文章。
输出格式
对于每组数据，输出一个占一行的整数，表示有多少个单词在文章中出现。
数据范围
输入样例：
输出样例：
1、自动机与的区别
2、推荐视频
视频讲解
3、算法步骤
自动机:在树的基础上，增加一个 失配 时用的指针，如果当前点匹配失败，则将指针转移到指针指向的地方，这样就可以不用重头再来, 尽可能的利用已经知道的信息，能少退就少退 , 指针的构建用 实现。
先根据模式串集合{,,,,}建立树,如图，然后拿着去匹配:
可以发现的是使用文本串在字典树上进行匹配的时候，找到了一个单词结点后还应该看看有没有以该单词结点的后缀为 前缀 的其他单词，比如的后缀是单词和的前缀。因此就需要一个 失配指针 在发现失配的时候指向其他存在的结点，就通过指针的指引，跳到这个位置，此时发现有黄色标识，就是又找到一个模式串,继续下一个字符,是,发现后续可以匹配,匹配了...
总的来说，自动机中失配指针和中数组的作用是一致的，就是 要想在只遍历一遍文本串的前提下，找到全部匹配模式串，就必须提前安排好匹配过程中失配后怎么办。如果在在树上构造 失配指针 ,就是学习如何构造自动机。
4、构建失配指针(构造自动机)
办法如下：
注释：类比,模式串的第一位，,退无可退，无法再退
直接和根结点相连的结点，如果这些结点失配，就只能重新开始匹配，故它们的指针指向根结点
其它结点，设当前结点为,其孩子结点为。要寻找的指针，需要看的指针指向的结点，假设是,要看的孩子中有没有和所代表的字符相同的，有则的指针指向的这个孩子结点，没有则继续沿着的指针往上走，如果找到相同，就指向，如果一直找到了根结点的也就是空的时候，的指针就指向，表示重新从根结点开始匹配。
考察的指针指向的结点有没有和相同的结点，否则继续往上，就保证了前缀是相同的，比如刚才寻找右侧的孩子结点的指针时，找到右侧的指针指向左侧的结点，他的孩子中有，就将右侧的孩子的指针指向它就保证了前缀是相同的。
这样，就用指针来安排好每次失配后应该跳到哪里，而指针跳到哪里，说明从根结点到这个结点之前的字符串已经匹配过了，从而避免了重复匹配，也就解决了只遍历一次文本串就找出所有单词的问题。
5、匹配过程
答：其实自动机就是一个数组构建的过程，由上到下去构建，还想不用循环防止每次都向上查询，就想着从上到下时把信息都填充完整，这样下面用时就不用担心了，（线性的思路啊~），也就是在第个节点填充时，它前面的都得是已经填充完整的状态，否则无法实现转移。
那如果现在不存在，那就啥不做的话，如果后续节点中有问它这个问题，想找是不是以出发有边时，它可以说没有，人家问那我继续找谁问啊，他说我也不知道，供应链条就断开了，这肯定不行。
本文地址：http://sjzytwl.xhstdz.com/quote/420.html 物流园资讯网 http://sjzytwl.xhstdz.com/ , 查看更多