AC算法是Alfred V.Aho（《编译原理》（龙书）的作者），和Margaret J.Corasick于1974年提出（与KMP算法同年）的一个经典的多模式匹配算法，可以保证对于给定的长度为n的文本，和模式集合P{p1,p2,…pm}，在O(n)时间复杂度内，找到文本中的所有目标模式，而与模式集合的规模m无关。正如KMP算法在单模式匹配方面的突出贡献一样，AC算法对于多模式匹配算法后续的发展也产生了深远的影响，而且更为重要的是，两者都是在对同一问题——模式串前缀的自包含问题的研究中，产生出来的，AC算法从某种程度上可以说是KMP算法在多模式环境下的扩展。在我的《KMP算法详解》一文中，我在最后已经提到，如果要用KMP算法匹配长度为n的文本中的m个模式，则需要为每一个模式维护一个next跳转表，在执行对文本的匹配过程中，我们需要关注所有这些next表的状态转移情况，这使得时间复杂度增长为O(mn)，对于较大的模式集合来说，这样的时间增长可能是无法接受的。AC算法解决了这一问题，通过对模式集合P的预处理，去除了模式集合的规模对匹配算法速度的影响。
要理解AC算法，仍然需要对KMP算法的透彻理解。这里我们还是以KMP算法中的老例子来说明前缀自包含如何在AC算法中发挥作用。对于模式串"abcabcacab"，我们知道非前缀子串abc(abca)cab是模式串的一个前缀(abca)bcacab，而非前缀子串ab(cabca)cab不是模式串abcabcacab的前缀，根据此点，我们构造了next结构，实现在匹配失败时的跳转。而对于多模式环境，这个情况会发生一定的变化。这里以AC论文中的例子加以说明，对于模式集合P{he，she，his，hers}，模式s(he)的非前缀子串he，实际上却是模式(he)，(he)rs的前缀。如果目标串target[i…i+2]与模式she匹配，同时也意味着target[i+1…i+2]与he，hers这两个模式的头两个字符匹配，所以此时对于target[i+3]，我们不需要回溯目标串的当前位置，而直接将其与he，hers两个模式的第3个字符对齐，然后直接向后继续执行匹配操作。
经典的AC算法由三部分构成，goto表，fail表和output表，goto表是由模式集合P中的所有模式构成的状态转移自动机，以上面的集合为例，其对应的goto结果如下，其中圆圈对应自动机的各个状态，边对应当前状态输入的字符。
对于给定的集合P{p1,p2,…pm}，构建goto表的步骤是，对于P中的每一个模式pi[1…j](1<=i<m+1)，按照其包含的字母从前到后依次输入自动机，起始状态D[0]，如果自动机的当前状态D[p]，对于pi中的当前字母pi[k](1<=k<=j)，没有可用的转移，则将状态机的总状态数smax+1，并将当前状态输入pi[k]后的转移位置，置为D[p][pi[k]] = smax，如果存在可用的转移方案D[p][pi[k]]=q，则转移到状态D[q]，同时取出模式串的下一个字母pi[k+1]，继续进行上面的判断过程。这里我们所说的没有可用的转移方案，等同于转移到状态机D的初始状态D[0]，即对于自动机状态D[p]，输入字符pi[k]，有D[p][pi[k]]=0。理论介绍很繁琐，让我们以之前的模式集合P{he，she，his，hers}说明一下goto表的构建过程。
第一步，将模式he加入goto表：
第二步，将模式she加入goto表：
第三步，将模式his加入goto表：
第四步，将模式hers加入goto表：
对于第一和第二步而言，两个模式没有重叠的前缀部分，所以每输入一个字符，都对应一个新状态。第三步时，我们发现，D[0][p3[1]]=D[0][‘h’]=1，所以对于新模式p3的首字母’h’，我们不需要新增加一个状态，而只需将D的当前状态转移到D[1]即可。而对于模式p4其前两个字符he使状态机转移至状态D[2]，所以其第三字符对应的状态D[8]就紧跟在D[2]之后。
goto表构建完成之后，我们就要构建fail表，所谓的fail表就是当我们处在状态机的某个状态D[p]时，此时的输入字符c使得D[p][c]=0，那么我们应该转移到状态机的哪个位置来继续进行呢。以输入文本"shers"为例，当输入到字母e时，我们会发现匹配模式(she)rs，对应与状态机的状态D[5]，然后输入字母r，此时我们发现D[6][‘r’]=0，对于字母r D[6]不存在有意义的跳转。此时我们不能跳转回状态D[0]，这样就会丢掉可能的匹配s(hers)。我们发现s(he)的后缀he是模式(he)rs的一个前缀，所以当匹配模式she时，实际也已经匹配了模式hers的前缀he，此时我们可以将状态D[6]转移到hers中的前缀he在goto表中的对应状态D[2]处，再向后执行跳转匹配。这一跳转，就是AC算法中的fail跳转，要实现正确的fail跳转，还需要满足一系列条件，下面会逐一说明。
对于模式串she，其在字母e之后发生了匹配失败，此时其对应的模式串（回溯到状态D[0]）就是she。对于she来说，它有两个包含后缀（除字符串自身外的所有后缀），he和e，对于后缀he，将其输入自动机D，从状态D[0]可以转移到状态D[2]，对于后缀e，没有可行的状态转移方案。所以对于状态D[5]，如果对于新输入的字符c没有可行的转移方案，我们可以跳转到状态D[2]，考察D[2][c]是否等于0.
AC两人在论文中举出的例子，并不能涵盖在构建fail时遇到的所有情况，这里特别说明一下。前面我们说过，对于she的包含后缀e，没有可行的转移方案，此时如果模式串中还包含一个模式era，那么D[5]可不可以转移到状态D[10]去呢，实际上这是不行的，我们需要找到的是当前所有包含后缀中最长的满足条件者（拗口），如果D[5]对于失败的输入c优先转移到D[10]，那么对于文本串shers，很显然会漏掉可能匹配hers，那么什么时机才应该转移到D[10]呢，当我们处理模式串hers时，处理到D[2]时对于之前的输入he，其最长的包含后缀是e，将e输入自动机，可以转移到D[10]，所以在D[2]处发生匹配失败的时候才应该转移到D[10]。所以当我们在D[5]处匹配失败时，要先跳转到D[2]如果再没有可用的转移，再跳转到D[10]。
才能做到人在旅途，感悟人生，享受人生。
