/*

Keywords Search

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 47775    Accepted Submission(s): 15220

 */

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int size,a[500001][27],T,shu[500001],dui[500001],fail[500001],sum;
bool f[500001];
char ch[100],s[1000008];
void jia()
{
int l=strlen(ch),now=1;
for(int i=0;i<l;i++)
if(a[now][ch[i]-‘a‘+1])
now=a[now][ch[i]-‘a‘+1];
else
{
size++;
now=a[now][ch[i]-‘a‘+1]=size;
}
shu[now]++;
return;
}
void shi()
{
dui[1]=1;
int h=0,t=1;
for(;h<t;)
{
h++;
int now=dui[h];
for(int i=1;i<=26;i++)
if(a[now][i])
{
int k=fail[now];
for(;!a[k][i];k=fail[k]);
fail[a[now][i]]=a[k][i];
t++;
dui[t]=a[now][i];
}
}
}
void jin()
{
int now=1,l=strlen(s);
for(int i=0;i<l;i++)
{
f[now]=1;
int k=s[i]-‘a‘+1;
for(;!a[now][k];now=fail[now]);
now=a[now][k];
if(!f[now])
for(int j=now;j;j=fail[j])
{
sum+=shu[j];
shu[j]=0;
}
}
printf("%d\n",sum);
}
int main()
{
for(int i=0;i<=26;i++)
a[0][i]=1;
scanf("%d",&T);
for(;T;T--)
{
size=1;
sum=0;
int n;
scanf("%d",&n);
for(;n;n--)
{
scanf("%s",ch);
jia();
}
shi();
scanf("%s",s);
jin();
for(int i=1;i<=size;i++)
{
f[i]=fail[i]=shu[i]=0;
for(int j=1;j<=26;j++)
a[i][j]=0;
}
}
return 0;
}

AC自动机 Keywords Search

原文：http://www.cnblogs.com/xydddd/p/5147234.html