<题目链接>
题目大意：
给你一些单词，和一个字符串，问你这个字符串中含有多少个上面的单词。
解题分析：
这是多模匹配问题，如果用KMP的话，对每一个单词，都跑一遍KMP，那么当单词数量非常多的时候，耗时会非常多，所以这里用到了AC自动机，这是一种类似于Trie树的数据结构，但是同时，它也用到了KMP算法中 next数组的思想。
本题可做模板：
#include <bits/stdc++.h> using namespace std; const int N = 5e5+5; int nxt[N][26],cnt[N],fail[N],pos; inline void insert(char *s){ int now=0; for(int i=0;s[i];++i){ int to=s[i]-'a'; if(!nxt[now][to])nxt[now][to]=++pos; now=nxt[now][to]; } ++cnt[now]; } /*构造失败指针的过程概括起来就一句话：设这个节点上的字母为C，沿着他父亲的失败指针走，直到走到一个节点，他的儿 子中也有字母为C的节点。然后把当前节点的失败指针指向那个字母也为C的儿子。如果一直走到了root都没找到，那就把失败 指针指向root。具体操作起来只需要：先把root加入队列(root的失败指针指向自己或者NULL)，这以后我们每处理一个 点，就把它的所有儿子加入队列*/ inline void getFail(){ memset(fail,0,sizeof(fail)); //fail指针初始化全部指向根节点 queue<int>q; for(int i=0;i<26;++i) if(nxt[0][i])q.push(nxt[0][i]); while(!q.empty()){ int now=q.front();q.pop(); for(int i=0;i<26;++i){ if(nxt[now][i])q.push(nxt[now][i]),fail[nxt[now][i]]=nxt[fail[now]][i]; //下一个元素的fail指针指向当前元素fail指针指向的元素对应的下一个元素 else nxt[now][i]=nxt[fail[now]][i]; } } } inline int query(char *s){ int now=0,res=0; for(int i=0;s[i];i++){ int tmp=nxt[now][s[i]-'a']; while(tmp){ if(cnt[tmp]>=0){ res+=cnt[tmp]; cnt[tmp]=-1; }else break; tmp=fail[tmp]; } now=nxt[now][s[i]-'a']; } return res; } char str[int(1e6+5)],s[55]; int main(){ int T;cin>>T; while(T--){ pos=0; memset(nxt,0,sizeof(nxt)); memset(cnt,0,sizeof(cnt)); int n;scanf("%d",&n); while(n--){ scanf("%s",s); insert(s); //将模式串插入trie图中 } getFail(); scanf("%s",str); printf("%d ",query(str)); } }