【问题描述】
给出由若干单词组成的字典（可能有相同的单词），再给出一篇文章（一个字符串），请计算有多少个不同的单词在字符串中出现。
【输入格式】
第1行一个正整数N。表示字典中单词的数目 接下来的N行，每行一个字符串（长度不超过50），表示一个单词。 最后一行为一个长字符串（长度不超过100000）。注意：单词和字符串均由小写字母构成。
【输出格式】
一行一个整数，表示长字符串中包含单词的数量。
【输入样例】
5 she he say shr her yasherhs
【输出样例】
3
【数据范围】
N<=40000
【来源】
hdu2222AC自动机
想了很久，今天终于静下心来把AC自动机学了。 AC自动机就是KMP的升级版，核心思想还是那个熟悉而神奇的失效数组，与KMP不同的是AC自动机能直接出来多个字符串，因为它直接是在一颗trie树上进行的加工。 trie树的相关介绍 算法核心就是先建立一颗trie树（具体方法介绍请参考上述链接），然后bfs遍历这棵树并进行失效数组的生成。 然后就和KMP一样遍历要找的字符串就可以得到答案了。
详细代码和细节如下：（f(i)为失效数组）
#include<cstdlib> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=2000005; int ch[maxn][26]={0},f[maxn],cnt=0,root,n,w[maxn]={0},q[maxn]; char s[100005]; void in()//建立trie树 { int p=root,i=0,k; while(1) { if(s[i]==0) { w[p]++; return; } int k=s[i]-'a'; if(!ch[p][k]) ch[p][k]=++cnt; p=ch[p][k]; i++; } } void get_fail()//生成失效数组 { int roor=0,frond=0; for(int i=0;i<26;i++) if(ch[root][i]) q[roor++]=ch[root][i],f[ch[root][i]]=0; while(roor!=frond) { int i=q[frond++]; for(int k=0;k<26;k++) { int j=ch[i][k]; if(!j){ch[i][k]=ch[f[i]][k];continue;} q[roor++]=j; //具体的生成操作 int c=f[i]; while(c&&ch[c][k]==0) c=f[c]; f[j]=ch[c][k]; } } } void init() { scanf("%d",&n); root=0; for(int i=1;i<=n;i++) { scanf("%s",s); in(); } get_fail(); } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); init(); scanf("%s",s); int l=strlen(s),ans=0,p=root; for(int i=0;i<l;i++)//遍历原字符串得到答案 { int k=s[i]-'a'; p=ch[p][k]; int now=p; while(now)//每一个失效位都要遍历 { if(w[now]) {ans++;w[now]=0;} now=f[now]; } } cout<<ans; return 0; }