AC自动机：Aho-Corasick automation，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法之一。要搞懂AC自动机，先得有模式树（字典树）Trie、广度优先策略和KMP模式匹配算法的基础知识。

关于AC自动机
建立Aho-Corasick automation算法需要三步：

  1. 建立模式串的Trie
  2. 给Trie添加失配路径
  3. 根据AC自动机，搜索待处理的文本

这里以航电OJ上的一道题hdu 2222 KeywordsSearch为例子。

1
给定5个单词:say she shr he her
2
一个字符串：yasherhs
3
问一共有多少单词在这个字符串中出现。
1
#include <stdio.h>
2
#include <stdlib.h>
3
#include <string.h>
4
struct Node
5
{
6
  int cnt;//是否为该单词的最后一个结点 
7
  Node *fail;//失败指针 
8
  Node *next[26];//Trie中每个结点的各个节点 
9
}*queue[500005];//队列，方便用BFS构造失败指针 
10
char s[1000005];//主字符串 
11
char keyword[55];//需要查找的单词 
12
Node *root;//头结点 
13
void Init(Node *root)//每个结点的初始化 
14
{
15
  root->cnt=0;
16
  root->fail=NULL;
17
  for(int i=0;i<26;i++)
18
    root->next[i]=NULL;
19
}
20
void Build_trie(char *keyword)//构建Trie树 
21
{
22
  Node *p,*q;
23
  int i,v;
24
  int len=strlen(keyword);
25
  for(i=0,p=root;i<len;i++)
26
  {
27
    v=keyword[i]-'a';
28
    if(p->next[v]==NULL)
29
    {
30
      q=(struct Node *)malloc(sizeof(Node));
31
      Init(q);
32
      p->next[v]=q;//结点链接 
33
    }
34
    p=p->next[v];//指针移动到下一个结点 
35
  }
36
  p->cnt++;//单词最后一个结点cnt++，代表一个单词 
37
}
38
void Build_AC_automation(Node *root)
39
{
40
  int head=0,tail=0;//队列头、尾指针 
41
  queue[head++]=root;//先将root入队 
42
  while(head!=tail)
43
  {
44
    Node *p=NULL;
45
    Node *temp=queue[tail++];//弹出队头结点 
46
    for(int i=0;i<26;i++)
47
    {
48
      if(temp->next[i]!=NULL)//找到实际存在的字符结点 
49
      { //temp->next[i] 为该结点，temp为其父结点 
50
        if(temp==root)//若是第一层中的字符结点，则把该结点的失败指针指向root 
51
          temp->next[i]->fail=root;
52
        else
53
        {
54
          //依次回溯该节点的父节点的失败指针直到某节点的next[i]与该节点相同，
55
                  //则把该节点的失败指针指向该next[i]节点； 
56
                  //若回溯到 root 都没有找到，则该节点的失败指针指向 root
57
          p=temp->fail;//将该结点的父结点的失败指针给p 
58
          while(p!=NULL)
59
          {
60
            if(p->next[i]!=NULL)
61
            {
62
              temp->next[i]->fail=p->next[i];
63
              break;
64
            }
65
            p=p->fail;
66
          }
67
          //让该结点的失败指针也指向root 
68
          if(p==NULL)
69
            temp->next[i]->fail=root;
70
        }
71
        queue[head++]=temp->next[i];//每处理一个结点，都让该结点的所有孩子依次入队 
72
      }
73
    }
74
  }
75
}
76
int query(Node *root)
77
{ //i为主串指针，p为模式串指针 
78
  int i,v,count=0;
79
  Node *p=root;
80
  int len=strlen(s);
81
  for(i=0;i<len;i++)
82
  {
83
    v=s[i]-'a';
84
    //由失败指针回溯查找，判断s[i]是否存在于Trie树中 
85
    while(p->next[v]==NULL && p!=root)
86
      p=p->fail;
87
    p=p->next[v];//找到后p指针指向该结点 
88
    if(p==NULL)//若指针返回为空，则没有找到与之匹配的字符 
89
      p=root;
90
    Node *temp=p;//匹配该结点后，沿其失败指针回溯，判断其它结点是否匹配 
91
    while(temp!=root)//匹配结束控制 
92
    {
93
      if(temp->cnt>=0)//判断该结点是否被访问 
94
      {
95
        count+=temp->cnt;//由于cnt初始化为 0，所以只有cnt>0时才统计了单词的个数 
96
        temp->cnt=-1;//标记已访问过 
97
      }
98
      else//结点已访问，退出循环 
99
        break;
100
      temp=temp->fail;//回溯 失败指针 继续寻找下一个满足条件的结点 
101
    }
102
  }
103
  return count;
104
}
105
int main()
106
{
107
  int T,n;
108
  scanf("%d",&T);
109
  while(T--)
110
  {
111
    root=(struct Node *)malloc(sizeof(Node));
112
    Init(root);
113
    scanf("%d",&n);
114
    for(int i=0;i<n;i++)
115
    {
116
      scanf("\n%s",keyword);
117
      Build_trie(keyword);
118
    }
119
    Build_AC_automation(root);
120
    scanf("\n%s",s);
121
    printf("%d\n",query(root));
122
  }
123
  return 0;
124
}