1. 多模匹配

AC自动机（Aho-Corasick Automaton）是多模匹配算法的一种。所谓多模匹配，是指在字符串匹配中，模式串有多个。前面所介绍的KMP、BM为单模匹配，即模式串只有一个。假设主串T[1⋯m]，模式串有k个P={P1,⋯,Pk}，且模式串集合的总长度为n。如果采用KMP来匹配多模式串，则算法复杂度为：

而KMP并没有利用到模式串之间的重复字符结构信息，每一次的匹配都需要将主串从头至尾扫描一遍。贝尔实验室的Aho与Corasick于1975年基于有限状态机（finite state machines）提出AC自动机算法[1]。小插曲：实际上AC算法比KMP提出要早，KMP是1977年才被提出来了的。

2. AC算法

AC自动机

自动机由状态（数字标记的圆圈）和转换（带标签的箭头）组成，每一次转换对应一个字符。AC算法的核心包括三个函数：goto、failure、output；这三个函数构成了AC自动机。对于模式串{he, his, hers, she}，goto函数表示字符按模式串的转移，暗含了模式串的共同前缀的字符结构信息，如下图：

failure函数表示匹配失败时退回的状态：

output函数表示模式串对应于自动机的状态：

完整的AC自动机如下：

匹配

AC算法根据自动机匹配模式串，过程比较简单：从主串的首字符、自动机的初始状态0开始，

• 若字符匹配成功，则按自动机的goto函数转移到下一状态；且若转移的状态对应有output函数，则输出已匹配上的模式串；
• 若字符匹配失败，则递归地按自动机的failure函数进行转移

匹配母串的算法如下：

构造

AC自动机的确简单高效，但是如何构造其对应的goto、failure、output函数呢？首先来看goto函数，细心一点我们发现goto函数本质上就是一棵带有回退指针的trie树，利用模式串的共同前缀信息，与output函数共同表示模式串的字符结构的信息。

failure函数是整个AC算法的精妙之处，用于匹配失败时的回溯；且回溯到的状态statestate应满足：状态statestate能按当前状态的转移字符进行能goto到的状态，且能构成最长匹配。记g(r,a)=s表示状态r可以按字符a goto到状态s，则称状态r为状态s的前一状态，字符a为状态s的转移字符。failure函数满足这样一个规律：当匹配失败时，回溯到的状态为前一状态的failure函数值（我们称之为failure转移状态）按转移字符能goto到的状态；若不能，则为前一状态的failure转移状态的failure转移状态按转移能goto到的状态；若不能，则为......上面的话听着有点拗口，让我们以上图AC自动机为例子来说明：

• 对于状态7，前一状态6的failure转移状态为0，状态0按转移字符s可以goto到状态3，所以状态7的failure函数f(7)=3；
• 对于状态2，前一状态1的failure转移状态为0，状态0按转移字符e可以goto到状态0，所以状态2的failure函数f(2)=0；

其中，所有root节点（状态0）能goto到的状态，其failure函数值均为0。根据goto表（trie树）的特性，可知某一状态的前一状态、转移字符是唯一确定的。因此定义β(s)=r表示状态s的前一状态为r，τ(s)=a指状态s的转移字符为a；记fi(s)=f(f(i−1)(s))。那么，状态s的failure函数的计算公式为：

在计算failure函数时，巧妙地运用队列进行递归构造，具体实现如下：

3. 实现

Talk is cheap, show me the code. Java版实现在这里；下面给出python实现（代码参考了 Implementation of the Aho-Corasick algorithm in Python）：

# coding=utf-8

from collections import deque, namedtuple



automaton = []

# state_id: int, value: char, goto: dict, failure: int, output: set

Node = namedtuple("Node", "state value goto failure output")





def init_trie(words):

    """

    creates an AC automaton, firstly create an empty trie, then add words to the trie

    and sets fail transitions

    """

    create_empty_trie()

    map(add_word, words)

    set_fail_transitions()





def create_empty_trie():

    """ initialize the root of the trie """

    automaton.append(Node(0, '', {}, 0, set()))





def add_word(word):

    """add word into trie"""

    node = automaton[0]

    for char in word:

        # char is not in trie

        if goto_state(node, char) is None:

            next_state = len(automaton)

            node.goto[char] = next_state  # modify goto(state, char)

            automaton.append(Node(next_state, char, {}, 0, set()))

            node = automaton[next_state]

        else:

            node = automaton[goto_state(node, char)]

    node.output.add(word)





def goto_state(node, char):

    """goto function"""

    if char in node.goto:

        return node.goto[char]

    else:

        return None





def set_fail_transitions():

    """construction of failure function, and update the output function"""

    queue = deque()

    # initialization

    for char in automaton[0].goto:

        s = automaton[0].goto[char]

        queue.append(s)

        automaton[s] = automaton[s]._replace(failure=0)

    while queue:

        r = queue.popleft()

        node = automaton[r]

        for a in node.goto:

            s = node.goto[a]

            queue.append(s)

            state = node.failure

            # failure transition recursively

            while goto_state(automaton[state], a) is None and state != 0:

                state = automaton[state].failure

            # except the chars in goto function, all chars transition will goto root node self

            if state == 0 and goto_state(automaton[state], a) is None:

                goto_a = 0

            else:

                goto_a = automaton[state].goto[a]

            automaton[s] = automaton[s]._replace(failure=goto_a)

            fs = automaton[s].failure

            automaton[s].output.update(automaton[fs].output)





def search_result(strings):

    """AC pattern matching machine"""

    result_set = set()

    node = automaton[0]

    for char in strings:

        while goto_state(node, char) is None and node.state != 0:

            node = automaton[node.failure]

        if node.state == 0 and goto_state(node, char) is None:

            node = automaton[0]

        else:

            node = automaton[goto_state(node, char)]

        if len(node.output) >= 1:

            result_set.update(node.output)

    return result_set





init_trie(['he', 'she', 'his', 'hers'])

print search_result("ushersm")

-------------------------------------------------------- 2016-06-14 更新 --------------------------------------------------------
实现了一个scala版本，支持添加词属性，代码托管在Github。

4. 参考资料

[1] Aho, Alfred V., and Margaret J. Corasick. "Efficient string matching: an aid to bibliographic search." Communications of the ACM 18.6 (1975): 333-340.
[2] Pekka Kilpeläinen, Lecture 4: Set Matching and Aho-Corasick Algorithm.