AC自动机，模板题， 参考：点这里
题目意思：
给出若干字符串，最后给出一个大的文本字符串，求前面的字符串，在文本字符串中一共出现了多少次
本题要点：
1、AC自动机
用若干模式串，建立字典树，同时为每一个字典树的每一个节点，建立 fail 数组。
2、查询文本串， 统计文本串中出现的模式串的次数。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int MaxN = 1000010, MaxM = 60;
char keyword[MaxM], textword[MaxN];
int trie[MaxN][26];
int cntWord[MaxN];
int fail[MaxN];
int cnt = 0;
int T, n;void insertWords(char s[], int len)
{
int root = 0;for(int i = 0; i < len; ++i){
int next = s[i] - 'a';if(!trie[root][next]){
trie[root][next] = ++cnt;}root = trie[root][next];}cntWord[root]++;
}void getFail()
{
queue<int> q;for(int i = 0; i < 26; ++i) //第二层的所有的字母加入队列{
if(trie[0][i]) {
fail[trie[0][i]] = 0;q.push(trie[0][i]);}}while(!q.empty()){
int now = q.front(); q.pop();for(int i = 0; i < 26; ++i) //查询26个字母{
if(trie[now][i]){
fail[trie[now][i]] = trie[fail[now]][i];q.push(trie[now][i]);}else{
trie[now][i] = trie[fail[now]][i];}}}
}int query(char s[], int len)
{
int now = 0, ans = 0;for(int i = 0; i < len; ++i){
now = trie[now][s[i] - 'a'];for(int j = now; j && cntWord[j] != -1; j = fail[j]){
ans += cntWord[j];cntWord[j] = -1; //遍历过后的节点标记，放置重复计算}}return ans;
}int main()
{
scanf("%d", &T);while(T--){
cnt = 0;memset(cntWord, 0, sizeof cntWord);memset(trie, 0, sizeof trie);scanf("%d", &n); for(int i = 0; i < n; ++i){
scanf("%s", keyword);insertWords(keyword, strlen(keyword));}getFail();scanf("%s", textword);printf("%d\n", query(textword, strlen(textword)));}return 0;
}/* 1 5 she he say shr her yasherhs *//* 3 */