笔试算法题（45）：简介

议题：AC自动机（Aho-Corasick Automation）

分析：

此算法在1975年产生于贝尔实验室，是著名的多模式匹配算法之一；一个常见的例子就是给定N个单词，给定包含M个字符的文章，要求确定多少个给定的单词在文章中出现过；AC自动机在匹配文本时不需要回溯，处理时间复杂度与pattern无关，仅是target的长度O(N)；构建AC自动机的时间复杂度；
与KMP算法类似，AC自动机也是利用前一个匹配模式串失效之后得到的信息来确定下一个匹配的开始位置，从而避免回移主串的匹配指针；与KMP算法不同的是，AC自动机是针对多个模式串在同一个主串上的匹配，不仅在同一个模式串匹配内部，而且在不同的模式串之间利用前一次匹配失效的信息来确定下一次匹配的开始位置；

AC自动机的构建主要由三个步骤：
针对所有模式串构建Trie树；
针对所有Trie树上的接点构建Fail指针：Fail指针指向的是如果当前节点匹配失败，则从通过Fail指针指向的新的节点开始匹配，但新的节点必须满足所在在新节点模式串的前缀必须是转移前的节点所在模式串的子串，也就是已经匹配成功的部分；
正式匹配过程：将主串在Trie树上匹配，主要有两种操作，如果当前节点匹配成功，则随机选择一条子路径到达的节点；如果当前节点匹配失败，则使用Fail指针转移到新的节点；知道文本末尾；

样例：

  1 /**
  2  * 定义Trie树中子节点的最大个数，26个英文字母
  3  * */
  4 const int MAX_NUM=26;
  5 /**
  6  * 用于构造Fail指针的队列，队列元素为拥有三个数据域
  7  * 的对象：
  8  * fail表示Fail指针
  9  * Child数组表示26个子节点指针
 10  * IsOver表示当前节点是否为一个单词的结束节点
 11  * */
 12 struct Node {
 13         Node *fail;
 14         Node *Child[MAX_NUM];
 15         int IsOver;
 16         Node() {
 17                 fail=NULL;
 18                 IsOver=0;
 19                 for(int i=0;i<26;i++)
 20                         Child[i]=NULL;
 21         }
 22 } *queue[1000];
 23 /**
 24  * pattern表示输入的单词
 25  * target表示目标匹配文本
 26  * */
 27 char pattern[100];
 28 char target[10000];
 29 
 30 /**
 31  * head表示队列queue中的头结点，新元素入队的位置
 32  * tail表示队列queue中的尾节点，元素出队的位置
 33  * */
 34 int head;
 35 int tail;
 36 
 37 /**
 38  * 首先利用pattern构建Trie树
 39  * Trie树的根节点root是一个包含空字符的辅助节点；
 40  * pointer指针遍历遍历Trie树
 41  * temp指针临时替换一个节点的26个子节点中的一个
 42  * index指针索引一个pattern中的字符
 43  * 如果有多个pattern字符串，则需要多次调用此方法
 44  * */
 45 void ConstructTrieTree(char *pattern, Node *root) {
 46         Node *pointer=root;
 47         Node *temp;
 48         char *index=pattern;
 49         /**
 50          * 此处循环以需要插入Trie树的pattern字符串作为依据
 51          * */
 52         while(*index!='') {
 53                 temp=pointer->Child[*index-'a'];
 54                 /**
 55                  * 如果某一个字符对应的指针为NULL，则创建对应的节点
 56                  * */
 57                 if(temp==NULL)
 58                         temp=new Node();
 59                 pointer=temp;
 60                 index++;
 61         }
 62         /**
 63          * 当index指针pattern末尾的时候循环结束；
 64          * 此时pointer指向pattern的最后一个字符所在的节点
 65          * */
 66         pointer->IsOver=1;
 67 }
 68 
 69 /**
 70  * 然后构造Fail指针：
 71  * 在Trie树上构建Fail指针的基本策略如同BFS遍历
 72  * 初始化将root入队，然后进入循环，循环检查队列是否为空，如果非空，则
 73  * 取出一个节点进行处理，并将该节点的所有子节点加入队列；如果队列为空，
 74  * 则算法结束；
 75  * 对节点进行处理就是寻找其Fail指针的指向位置
 76  * 如果当前节点的字符为A，则跳转到当前节点的父节点的fail指针指向的节点
 77  * 处，判断其儿子中是否有为A字符的节点，如果没有则继续按照其自身的fail
 78  * 指针指向的节点跳转，直到找到字符为A的节点或者到达root节点处
 79  * */
 80 void ConstructFailPointer(Node *root, Node **queue) {
 81         /**
 82          * 初始化root节点的fail指针，并将其入队queue
 83          * */
 84         head=0;tail=0;
 85         root->fail=NULL;
 86         queue[head++]=root;
 87 
 88         Node *temp;
 89         Node *index;
 90         while(head!=tail) {
 91                 /**
 92                  * 从队列末尾获取一个节点
 93                  * */
 94                 temp=queue[tail++];
 95                 index=NULL;
 96                 for(int i=0;i<26;i++) {
 97                         /**
 98                          * 处理当前节点，遍历其Child指针数组
 99                          * */
100                         if(temp->Child[i]!=NULL) {
101                                 /**
102                                  * 对于root节点的直接子节点而言，由于他们没有
103                                  * 任何前缀而言，所以其fail指针都指向root节点
104                                  * */
105                                 if(temp==root)
106                                         temp->Child[i]->fail=root;
107                                 else {
108                                         index=temp->fail;
109                                         while(index!=NULL) {
110                                                 /**
111                                                  * 循环访问当前节点的fail指针指向的节点
112                                                  * 考察其子节点中的Child[i]是否存在，也就是
113                                                  * 是否有相同的字符
114                                                  * */
115                                                 if(index->Child[i]!=NULL) {
116                                                         /**
117                                                          * Child[i]表示当前处理的字符子节点
118                                                          * temp表示原始父亲节点
119                                                          * index表示根据fail指针跳转的节点
120                                                          * */
121                                                         temp->Child[i]->fail=index->Child[i];
122                                                         break;
123                                                 }
124                                                 index=index->fail;
125                                         }
126                                         /**
127                                          * root节点的fail指针初始化为NULL
128                                          * */
129                                         if(index==NULL)
130                                                 temp->Child[i]->fail=root;
131                                 }
132                                 /**
133                                  * 将temp节点的子节点入队queue
134                                  * */
135                                 queue[head++]=temp->Child[i];
136                         }
137                 }
138         }
139 }
140 
141 /**
142  * 最后正式施行字符串匹配操作：
143  * 利用Trie树（已经将所有的Pattern串插入）与target文本串进行匹配，有两种情况：
144  * 1. 如果某一个节点的Child[i]对应target的字符存在，则下到子节点
145  * 2. 如果某一个节点的所有子节点Child[i]都没有与target的字符匹配的，则使用fail跳转
146  * 匹配函数最终返回pattern数组中单词在target文本串中出现的个数
147  * */
148 int MultiPatternSearch(Node *root, char *target) {
149         char *index1=target;
150         Node *index2=root;
151         Node *temp;
152         int i=0, count=0;
153         while(index1[i]!='') {
154                 /**
155                  * 如果不能匹配则跳转到fail指针指向的节点
156                  * */
157                 while(index2->Child[index1[i]-'a']==NULL && index2!=root)
158                         index2=index2->fail;
159                 /**
160                  * 准备匹配下一个字符，但如果上述循环是因为后面一个条件结束，则index2
161                  * 需要重新指向root
162                  * */
163                 index2=index2->Child[index1[i]-'a'];
164                 if(index2==NULL)
165                         index2=root;
166                 temp=index2;
167                 while(temp!=root && temp->IsOver==1) {
168                         count++;
169                         /**
170                          * 如果Trie树中的一个pattern成功匹配，则需要
171                          * 将其IsOver域设置成0，防止重复匹配；
172                          * 然后跳转到与其具有公共前缀的fail指针指向的节点
173                          * 继续进行匹配
174                          * */
175                         temp->IsOver=0;
176                         temp=temp->fail;
177                 }
178                 i++;
179         }
180         return count;
181 }

参考链接：
http://www.cppblog.com/mythit/archive/2009/04/21/80633.html
http://www.zhiwenweb.cn/Category/Security/1274.htm