曲江二首一、概述
AC算法是一个经典的多模式匹配算法，可以保证对于给定的长度为n的文本，和模式集合P{p1,p2,...pm}，在O(n)时间复杂度内，找到文本中的所有目标模式，而与模式集合的规模m无关。要理解AC算法，仍然需要对KMP算法的透彻理解。
KMP中我们用两个指针i和j分别表示，A[i-j+ 1..i]（目标串）与B[1..j]（模式串）完全相等。也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前j个字符，当A[i+1]≠B[j+1]，KMP 的策略是调整j的位置（减小j值）使得A[i-j+1..i]与B[1..j]保持匹配且新的B[j+1]恰好与A[i+1]匹配，而next函数恰恰记录了这个j应该调整到的位置。同样AC自动机的失败指针具有同样的功能，也就是说当我们的模式串在Tire上进行匹配时，如果与当前节点的关键字不能继续匹配的时候，就应该去当前节点的失败指针所指向的节点继续进行匹配。算法就是这样应用有限自动机巧妙地将字符比较转化为了状态转移。
路桥实验中学
此算法有两个特点，一个是扫描文本时完全不需要回溯，另一个是时间复杂度为O(n)，时间复杂度与关键字的数目和长度无关，但所需时间和文本长度以及所有关键字的总长度成正比。
AC算法有三个主要步骤，一个是字典树tire的构造（即构造转向函数），一个是搜索路径的确定（即构造失败函数），还有就是模式匹配过程。
二、AC算法思想
算法的基本思想是这样的：核心运动
●在预处理阶段，AC自动机算法建立了三个函数，转向函数goto，失效函数
failure和输出函数output，由此构造了一个树型有限自动机。
●在搜索查找阶段，则通过这三个函数的交叉使用扫描文本，定位出关键字在文
本中的所有出现位置。
下图是多模式{he， she， his ，hers}构成的一个确定性有限状态机，做几点说明：
图 2.1
1、该状态机优先按照实线标注的状态转换路径进行转换，当所有实线标注的状态转换路径条件不能满足时，按照虚线的状态转换路径进行状态转换。如：状态0时，当输入h，则转换到状态1；输入s，则转换到状态3；否则转换到状态0。
2、匹配过程如下：从状态0开始进行状态转换，主串作为输入。如主串为：ushers，状态转换的过程是这样的：
图2.2
3、当状态转移到2，5，7，9等红色状态点时，说明发生了模式匹配。
木兰诗教学设计
如主串为：ushers，则在状态5、2、9等状态时发生模式匹配，匹配的模式串有she、he、hers。
定义：
在预处理阶段，AC自动机算法建立了三个函数，转向函数goto，失效函数failure 和输出函数output，由此构造了一个树型有限自动机。
转向函数，指的是一种状态之间的转向关系。g(pre, x)=next：状态pre在输入一个字符x后转换为状态next（上图中的实线部分）。
失效函数，指的也是状态和状态之间一种转向关系。f(per)=next：是在比较失配的情况下使用的转换关系。在构造转向函数时，还缺少许多转换，即当状态机在状态pre 输入字符y后不知道该往哪转了。所以就要在状态机中找到一个有意义的状态，当出现这种情况时，自动切换到那个状态。
10以内的加减法
输出函数，指的是状态和模式串之间的一种关系。output(i)={P}，表示当状态机到达状态i时，模式串集合{P}中的所有模式串可能已经完成匹配。
小班建构区目标例：
模式串为{he， she， his ，hers} 时，如图2.4所示。
转向函数：
失效函数：
输出函数：
三、字典树tire的构造
这个比较好理解，就是把要匹配的一些字符串添加到树结构中去。树边就是单词中的字符，单词中最后一个字符的连接节点添加标志is_final_state，以表示改节点路径包含1个模式串中的字符串，搜索到此节点就表示找到了模式串中的某个单词，可以直接输出。Trie是一个树形结构的状态装换图，从一个结点到它的各个子结点的边上有不同的标号。Trie的叶子结点表示识别到的关键字。
对于给定的集合P{p1,p2,...pm}，构建goto表的步骤是，对于P中的每一个模式j](1<=i<m
+1)，按照其包含的字母从前到后依次输入自动机，起始状态root，如果自动机的当前状态temp，对于PatternSet[i]中的当前字母
ch=PatternSet[i][k](1<=k<=j)，没有可用的转移，则将状态机的总状态数STATE_NO+1，新建状态ch为new_state，并将当前状态temp输入ch后的转移位置置为
new_state->state_no = STATE_NO，如果存在可用的转移方案temp->goto[ch]=q，则转移到状态q，同时取出模式串的下一个字母PatternSet[i][k+1]，继续进行上面的判断过程。怎样清洗冰箱
理论介绍很繁琐，让我们以之前的模式集合P{he，she，his，hers}说明一下goto 表的构建过程。
第一步，将模式he加入goto表：
第二步，将模式she加入goto表：
第三步，将模式his加入goto表：
第四步，将模式hers加入goto表：
对于第一和第二步而言，两个模式没有重叠的前缀部分，所以每输入一个字符，都对应一个新状态。第三步时，我们发现，女性名人名字大全
temp->goto[PatternSet[3]]=temp->goto[‘h’]=1，所以对于新模式PatternSet[3]的首字母'h'，我们不需要新增加一个状态，而只需将root的当前状态转移到状态状态state[1]即可。而对于模式PatternSet[4]其前两个字符he使状态机转移至状态state[2]，所以其第三字符对应的状态state[8]就紧跟在state[2]之后。
AC算法中的output表，在构建goto表的过程中，我们知道，状态2，5，7，9是输入的4个模式串的末尾部分，所以如果在执行匹配过程中，达到了如下四个状态，我们就知道对应的模式串被发现了。对于状态机的某些状态，对应某个完整的模式串已经被发现，我们就用output表来记录这一信息。完成goto表的构建后，状态机中各状态对应的output表的情况如下：
2 he
5 she，he
7 his
9 hers
四、搜索路径的确定（失败函数的构建）
goto表构建完成之后，我们就要构建fail表，所谓的fail表就是当我们处在状态机的某个状态state[p]时，此时的输入字符c使得state[p]->goto[c]=NULL，那么我们应该转移到状态机的哪个位置来继续进行呢。以输入文本"shers"为例，当输入到字母e时，我们会发现匹配模式(she)rs，对应与状态机的状态state[5]，然后输入字母r，此时我们发现state[6]->goto['r']=NULL，对于字母r state[6]不存在有意义的跳转。此时我们不能跳转回状态state[0]，这样就会丢掉可能的匹配s(hers)。我们发现s(he)的后缀he是模式(he)rs的一个前缀，所以当匹配模式she时，实际也已经匹配了模式hers的前缀he，此时我们可以将状态state[6]转移到hers中的前缀he在goto 表中的对应状态state[2]处，再向后执行跳转匹配。这一跳转，就是AC算法中的fail 跳转，要实现正确的fail跳转，还需要满足一系列条件，下面会逐一说明。
对于模式串she，其在字母e之后发生了匹配失败，此时其对应的模式串（回溯到状态state[0]）就是she。对于she来说，它有两个包含后缀（除字符串自身外的所有后缀），he和e，对于后缀he，将其输入自动机state，从状态state[0]可以转移到状态state[2]，对于后缀e，没有可行的状态转移方案。所以对于状态state[5]，如果对于新输入的字符c没有可行的转移方案，我们可以跳转到状态state[2]，考察
state[2]->goto[c]是否等于NULL.
AC两人在论文中举出的例子，并不能涵盖在构建fail时遇到的所有情况，这里特别说明一下。前面我们说过，对于she的包含后缀e，没有可行的转移方案，此时如果模式串中还包含一个模式era，那么state[5]可不可以转移到状态state[10]去呢，实际上这是不行的，我们需要找到的是当前所有包含后缀中最长的满足条件者（拗口），如果state[5]对于失败的输入c优先转移到state[10]，那么对于文本串shers，很显然会漏掉可能匹配hers，那么什么时机才应该转移到state[10]呢，当我们处理模式串hers时，处理到state[2]时对于之前的输入he，其最长的包含后缀是e，将e输入自动机，可以转移到state[10]，所以在state[2]处发生匹配失败的时候才应该转移到state[10]。所以当我们在state[5]处匹配失败时，要先跳转到state[2]如果再没有可用的转移，再跳转到state[10]。
这个例子同时说明，对于模式集合P的所有模式PatternSet[]，我们需要处理的不仅是PatternSet[i]的所
有包含后缀，而是PatternSet[i]的所有非前缀子串。以模式hers为例，其在2，8，9三个状态都可能发生匹配失败，所以我们要提取出hers的所有非前缀子串(e，er，r，ers，rs，s)，然后按照这些子串的末尾字符所对应的自动机状态分组（上例就可以分组为{e}对应状态2，{er，r}对应状态8，{ers，rs，s}对应状态9），然后分别将这些组中的子串从state[0]开始执行状态转移，直到没有可行的
