题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1277
推荐一篇博客（看思路就可以，实现用的是java）：
https://www.cnblogs.com/nullzx/p/7499397.html
这是一道模板题，拿来练手，之前看了一篇博客，有点错误，但是hdu上面居然过了，最主要的是我在hdu上面三道AC自动机模板题都是这个错的代码，居然都过了，害的我纠结了一晚上，原来是数据太水了。
主要还是看上面的博客，写了点注释，不一定对，以后好拿来复习。
代码（指针版）：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<set>
#include<cstdio>
#include<string>
#include<deque>
using namespace std;
typedef long long LL;
#define eps 1e-8
#define INF 0x3f3f3f3f
#define maxn 10005
char str[maxn][];
char s[];
struct node{
int id;//记录当前关键字的编号
node *next[];//指向儿子
node *fail;//失配后指向的地方，相当于KMP里面的next数组的作用
node(){
id=-;
memset(next,,sizeof(next));
fail=NULL;
}
};
queue<int>qe;//记录出现的关键字编号
queue<node*>q;//BFS
int n,m,k,t;
void insert(char *s,node *root,int ID){//插入关键字到trie里面
node *p=root;
int len=strlen(s);
for(int i=;i<len;i++){
int id=s[i]-'';
if(p->next[id]==NULL)
p->next[id]=new node();
p=p->next[id];
}
p->id=ID;//在关键字结束的地方把id更新为关键字的ID
}
void build_fail(node *root){//构建fail指针，要和KMP算法联想起来作比较
while(!q.empty())
q.pop();
q.push(root);
while(!q.empty()){
node *temp=q.front();
q.pop();
for(int i=;i<;i++){
if(temp->next[i]==NULL)
continue;
if(temp==root)//让root节点的所有儿子的fail指针都指向root，相当于next[0]=-1
temp->next[i]->fail=root;
else{
node *p=temp->fail;//把temp->fail赋给p，因为接下来p要改变
while(p!=NULL){//一直向fail方向走，直到找到某个点的next[i]!=NULL或者p==NULL(找不到)
if(p->next[i]!=NULL){
temp->next[i]->fail=p->next[i];
break;
}
p=p->fail;
}
if(p==NULL)//如果找不到，就让temp的儿子i的fail指针指向根
temp->next[i]->fail=root;
}
q.push(temp->next[i]);
}
}
}
void query(node *root){
while(!qe.empty())
qe.pop();
node *temp=root;
for(int i=;i<n;i++){
for(int j=;j<;j++){
int id=str[i][j]-'';
//一直往fail指向的方向找，直到找到或者到了root，相当于KMP里面K一直等于next[K]，最后匹配成功或者K=-1
while(temp->next[id]==NULL&&temp!=root)
temp=temp->fail;
temp=temp->next[id];//temp下移
if(temp==NULL)
temp=root;
node *p=temp;
while(p!=root){//在所有的以i+'0'字符结尾的前缀里面找以这个字符结束的单词
if(p->id!=-){//注意这个p->id的位置，刚刚学，看了错的博客，把它写在了上面，hdu居然过了，纠结了我老半天
qe.push(p->id);
p->id=-;//因为可能会有多个后缀和某一个前缀相同，可能会重复计数，所以我们要标记一下
}
p=p->fail;
}
}
}
}
void destroy(node *root){
if(root==NULL)
return;
for(int i=;i<;i++){
if(root->next[i]!=NULL)
destroy(root->next[i]);
}
delete root;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF){
node *root=new node();
for(int i=;i<n;i++)
scanf("%s",str[i]);
getchar();
char c;
for(int i=;i<m;i++){
int num=;//计算空格数量，一旦达到了三个就说明接下来开始输入关键字了
while(num!=&&(c=getchar())){
if(c==' ')
num++;
}
scanf("%s",s);//输入关键字
insert(s,root,i);//把关键字插入字典树
}
build_fail(root);//构建fail指针
query(root);//扫描
if(qe.size()==)
printf("No key can be found !\n");
else{
printf("Found key:");
while(!qe.empty()){
printf(" [Key No. %d]",qe.front()+);
qe.pop();
}
printf("\n");
}
destroy(root);//释放内存
}
return ;
}
代码（数组版）：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<set>
#include<cstdio>
#include<string>
#include<deque>
using namespace std;
typedef long long LL;
#define eps 1e-8
#define INF 0x3f3f3f3f
#define maxn 600005
int trie[maxn][],fail[maxn],val[maxn],ID[maxn];
char str[][],s[];
int n,m,t,cnt;
queue<int>q;
void init(){
memset(trie,,sizeof(trie));
memset(fail,,sizeof(fail));//让所有点的fail都指向0(根节点)
memset(val,,sizeof(val));
cnt=;
}
void insert(char *s,int k){
int root=;
for(int i=;s[i];i++){
int id=s[i]-'';
if(trie[root][id]==)
trie[root][id]=++cnt;
root=trie[root][id];
}
val[root]++;//标记单词结尾
ID[root]=k;//记录ID
}
void build_fail(){//构建fail指针
while(!q.empty())
q.pop();
int root=;
for(int i=;i<;i++){//把root的儿子都压入队列
if(trie[root][i])
q.push(trie[root][i]);
}
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=;i<;i++){
if(trie[u][i]){//如果u的儿子i存在，然它儿子的fail指向fail[u]的儿子，并压入队列
fail[trie[u][i]]=trie[fail[u]][i];
q.push(trie[u][i]);
}else{//如果不存在，把fail[u]的儿子i变成u的儿子
trie[u][i]=trie[fail[u]][i];
}
}
}
}
void query(){
while(!q.empty())
q.pop();
int u=;
for(int i=;i<n;i++){
for(int j=;j<;j++){
int id=str[i][j]-'';
u=trie[u][id];//u在trie树上往下移
int temp=u;//临时保存u
while(temp!=){//遍历temp和它的fail指向的所有以str[i][j]结尾的前缀，看里面有多少个是单词结尾，这里可以加一个&&val[temp]!=0优化一下
if(val[temp]){//如果是单词结尾
q.push(ID[temp]);//压进队列
val[temp]=;//把标记去掉，防止重复计算
}
temp=fail[temp];//往fail方向走，直到回到根节点
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF){
init();
for(int i=;i<n;i++){
scanf("%s",str[i]);
}
getchar();
for(int i=;i<m;i++){
int num=;
char c;
while(num!=&&(c=getchar())){
if(c==' '){
num++;
continue;
}
}
scanf("%s",s);
insert(s,i);
}
build_fail();
query();
if(q.size()==)
printf("No key can be found !\n");
else{
printf("Found key:");
while(!q.empty()){
printf(" [Key No. %d]",q.front()+);
q.pop();
}
printf("\n");
}
}
return ;
}