Description
给你N个单词，然后给定一个字符串，问一共有多少单词在这个字符串中出现过（输入相同的字符串算不同的单词，同一个单词重复出现只计一次）。
Input
第一行一个整数N，表示给定单词的个数。
接下来N行，每行输入一个长度不超过50且全由小写字母组成的单词。 最后一行输入一个长度不超过1000000的字符串。 N≤10000Output
输出一行包含一个整数，表示共在给定字符串中出现过的单词个数。
样例：
Input
5
she he say shr her yasherhsOutput
3
关于AC自动机:
Aho-Corasick automaton，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法。
假设我们已经学会了Trie树，类似于KMP算法的，我们对于树上的每个节点，处理出在此 节点下后，在树上应该跳转到的点，用nxt数组记录；那么，如何求出nxt数组呢？？？
首先，如果x接下来要匹配的字符与now节点直接相连，那我们肯定直接跳到下一个节点。 如果当前字符无法继续匹配，就跳到now节点的nxt的与此字符对应的节点上去 然后，与根节点直接相连的节点就直接预处理一下就好了。例：对于样例，我们先建一棵Trie树（图中加着重号的为每个单词的终止节点）
将所有根节点的子节点的nxt数组指向根节点，再将这些节点加入队列。
然会对于队列里的每一个节点，从a枚举到z,如果当前结点没有这个字符儿子 就将它指向它的nxt节点的儿子,这样我们就成功的将Trie树建成了Trie图
处理出来就是这样知道，然后对文本串依次遍历匹配，统计答案就可以了 code:
#include#define N 1001000using namespace std;int cnt,n;int tree[N],dl[N],num[N],net[N],son[N][30];char s1[N],s2[N];void ins(){//建Trie树 int now=0,l=strlen(s1+1); for(int i=1;i<=l;i++){ if(!son[now][s1[i]-'a'+1]) son[now][s1[i]-'a'+1]=++cnt; now=son[now][s1[i]-'a'+1]; } num[now]++;//记录单词尾}void get_net(){ int t=1,w=0; for(int i=1;i<=26;i++) if(son[0][i])dl[++w]=son[0][i];//预处理与根节点相连的节点 while(t<=w){//BFS处理net数组 int now=dl[t]; for(int i=1;i<=26;i++){ if(!son[now][i])son[now][i]=son[net[now]][i]; else{ net[son[now][i]]=son[net[now]][i]; dl[++w]=son[now][i]; } } t++; }}void fuck(){ int now=0,ans=0,l=strlen(s2+1); for(int i=1;i<=l;i++){ now=son[now][s2[i]-'a'+1]; int to=now; while(to!=0&&num[to]!=-1){ ans+=num[to]; num[to]=-1;//已经统计过的单词不要再次统计 to=net[to]; } } printf("%d\n",ans);}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){scanf("%s",s1+1);ins();} get_net();scanf("%s",s2+1); fuck(); return 0;}
蒟蒻题解，欢迎指正；
水平太低，大佬勿喷；