题目地址：HDU 2222
AC自动机第一发！真好奇这些算法是怎么被发明的。。算法的魅力真是无穷。
这题是AC自动机模板题。自己实在写不出来，比着kuangbin的模板写的= =
代码如下：
#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
#include <string>
#include <time.h>
using namespace std;
#define LL long long
#define pi acos(-1.0)
#pragma comment(linker, "/STACK:1024000000")
const int mod=9901;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
const int MAXN=1000000+300;
char s[MAXN];
struct Tire
{
int next[500010][30], fail[500010], flag[500010];
int root, L;
int newnode()
{
for(int i=0;i<26;i++){
next[L][i]=-1;
}
flag[L++]=0;
return L-1;
}
void init()
{
L=0;
root=newnode();
}
void Insert(char s[])
{
int len=strlen(s), x, i, now=root;
for(i=0;i<len;i++){
x=s[i]-'a';
if(next[now][x]==-1){
next[now][x]=newnode();
}
now=next[now][x];
}
flag[now]++;
}
void Build()
{
queue<int>q;
fail[root]=root;
for(int i=0;i<26;i++){
int v=next[root][i];
if(v==-1){
v=root;
}
else{
fail[v]=root;
q.push(v);
}
}
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<26;i++){
int v=next[u][i];
if(v==-1){
next[u][i]=next[fail[u]][i];
}
else{
fail[v]=next[fail[u]][i];
q.push(v);
}
}
}
}
int Query(char s[])
{
int len=strlen(s), ans=0;
int now=root, x;
for(int i=0;i<len;i++){
x=s[i]-'a';
now=next[now][x];
int tmp=now;
while(tmp!=root){
ans+=flag[tmp];
flag[tmp]=0;
tmp=fail[tmp];
}
}
return ans;
}
}ac;
int main()
{
int t, n, i;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
ac.init();
for(i=0;i<n;i++){
scanf("%s",s);
ac.Insert(s);
}
ac.Build();
scanf("%s",s);
printf("%d\n",ac.Query(s));
}
return 0;
}