SSOJ2759KeywordsSearch
1538+
作者：crxis 发布：2020-12-28 分类：AC自动机
题目大意：n个单词和一篇长度为m的文章，请问有多少个单词在文章中程序过？
题目描述
给定 n 个长度不超过 50 的由小写英文字母组成的单词准备查询，以及一篇长为 m 的文章，问：文中出现了多少个待查询的单词。多组数据。
输入
第一行一个整数 T，表示数据组数；
对于每组数据，第一行一个整数 n，接下去 n 行表示 n 个单词，最后一行输入一个字符串，表示文章。
输出
对于每组数据，输出一个数，表示文中出现了多少个待查询的单词。
提示
样例输入
1
5
she
he
say
shr
her
yasherhs样例输出
3对于全部数据，1≤n≤104,1≤m≤106。
解题思路
一个字符串，跟多个字符串进行匹配，可以使用AC自动机：首先对单词建立Trie树，然后根据KMP的原理，预处理每一条链的最长公共前后缀——匹配不成功，往回退到哪里？保存到p数组。
因为长度大退到长度小，所以应该按照深度从小到大处理，即使用广搜。
最后匹配的时候，可能出现单词包含现象，因此匹配的最长公共前后缀，还需要继续往回找，看一下短一点的公共前后缀是否是单词，此处可以记忆化，否则往回退的次数约单词长度。
程序实现
