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

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

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

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

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