AC 自动机

前缀函数以及 KMP 算法很好的处理了单个模式串和文本串之间的字符匹配问题，但是如果存在多个模式串对于单个文本串进行匹配时，每个模式串都要和文本串进行一次预处理，时间复杂度为 O(n(∣T∣+∣S∣))O(n (|T| + |S|))，nn 为模式串个数，∣T∣,∣S∣|T|,|S| 为模式串和文本串长度。

而 AC 自动机很好的解决了这个问题，AC 自动机（Aho-Corasick Automaton）是一种同样利用了 KMP 思想，以 Tire 树为结构的多模式匹配算法。

算法过程

AC 自动机的过程分为两步：建立 Trie 树以及预处理失配指针。

建立 Trie 树

不多赘述，Trie 树上的每一个节点表示某一个模式串的前缀。

1
2
3
4
5
6
7
8
9
10
inline void insert(char *str)
{
    int cur = 0, len = strlen(str);
    for (int i = 0; i < len; i ++)
    {
        int k = str[i] - 'a';
        if (!tr[cur][k]) tr[cur][k] = ++ idx;
        cur = tr[cur][k];
    }
}

处理失配指针

失配指针，又称为 failfail 指针，本质即为 KMP 算法中的 nextnext 辅助数组。

我们知道，KMP 算法中的 next[]next[] 中记录着每一个前缀字符串的最长 borderborder 值，AC 自动机的 failfail 数组同样如此。failufail_u 表示状态 uu 的指针，指向着状态 uu 的最大 border 值所处的状态（因为存在多个模式串，他们的 borderborder 相互交叉），然而 Trie 树上每一个节点的状态刚好就是每一个模式串可能的所有前缀集合。

因此，AC 自动机的失配指针指向当前状态的最长后缀状态。

拿 OI-Wiki 的图举个例子：

节点 66 的状态为 his\texttt{his}，它的失配指针 fail6=7fail_6 = 7 的状态为 s\texttt{s}，满足定义。

节点 99 的状态为 she\texttt{she}，它的失配指针 fail9=2fail_9 = 2 的状态为 he\texttt{he}，满足定义。

那么如何构建呢？

首先一个显然的性质，一个 Trie 树上某一个节点的 failfail 指针必然指向深度小于它的节点，因此可以使用 bfs 的框架。

其次，就像我们在 KMP 预处理 next1←0next_1 \gets 0 一样，Trie 树的第二层（根节点为第一层）不存在匹配，因此直接指向 00。

剩下的每一层，不难发现会有继承关系，就像上图所示的 fail8=1,fail9=2fail_8 = 1, fail_9 = 2，通过前缀函数定义显然易证。因此让每一个当前节点的 fail 指向它的父亲节点的 fail 指针的这一个下标，代码语言可以写为：

1
cur -> son[k] -> fail = cur -> fail -> son[k];

以上是在有这个节点的情况下，如果不存在而不去处理，后面的 bfs 的 failfail 数组很可能指向这里，因此我们还要把不存在的这个节点直接当作之前所说的哪一个节点，即：

1
cur -> son[k] = cur -> fail -> son[k];

像这样，后面的 failfail 如果跳到了 curcur 上的 sonkson_k，就会直接跳向 failcurfail_{cur} 上的 sonkson_k 了。

之所以不用考虑边界问题，是因为不存在的默认置 00 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline void build()
{
    hh = 0, tt = -1;
    for (int k = 0; k < 26; k ++)
        if (tr[0][k]) fail[tr[0][k]] = 0, que[++ tt] = tr[0][k];
    while (hh <= tt)
    {
        int cur = que[hh ++];
        for (int k = 0; k < 26; k ++)
        {
            if (tr[cur][k]) fail[tr[cur][k]] = tr[fail[cur]][k], que[++ tt] = tr[cur][k];
            else tr[cur][k] = tr[fail[cur]][k];
        }
    }
}

多模式匹配

对于查询的文本串 TT，我们只需要在处理好的 Trie 树上走一遍，对于每一个走到的状态，这个状态都是 TT 的前缀，因此这个状态和包括所有的 failfail 指针都匹配上了 TT，按照要求处理即可。

比如 P3808 AC 自动机（简单版） - 洛谷 | 计算机科学教育新生态 中的查询：

1
2
3
4
5
6
7
8
9
10
11
12
int query(char *str)
{
    int cur = 0, ans = 0, len = strlen(str);
    for (int i = 0; i < len; i ++)
    {
        int k = str[i] - 'a';
        cur = tr[cur][k];
        for (int temp = cur; temp && ~cnt[temp]; temp = fail[temp])
            ans += cnt[temp], cnt[temp] = -1;
    }
    return ans;
}

P3796 AC 自动机（简单版 II） - 洛谷 | 计算机科学教育新生态 中：

1
2
3
4
5
6
7
8
9
10
void query(char *str)
{
    int cur = 0, len = strlen(str);
    for (int i = 0; i < len; i ++)
    {
        cur = tr[cur][str[i] - 'a'];
        for (int temp = cur; temp; temp = fail[temp])
            ans[rec[temp]].cnt ++;
    }
}

实际上这样的复杂度是错误的，和 KMP 算法中的一样，不断地跳 nextnext 时间复杂度为 O(∣S∣)O(|S|)，因此此时的 AC 自动机时间复杂度达到了 O(∑∣S∣×∣T∣)O(\textstyle{\sum}|S| \times |T|)，因此我们需要优化。

效率优化

之前说到，一个状态的 failfail 深度小于这个状态的深度，又由于每一个点只有一个 failfail 指针，每个点互相之间应当联通，因此可以证明：

Trie 树上只保留 failfail 的情况下是一棵树，根节点为 00。

因此暴力跳 failfail 的过程变为了在一棵树上求和的过程，用 拓扑排序 或者 bfs 都可以。

P5357 【模板】AC 自动机 - 洛谷 | 计算机科学教育新生态 Code:

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
struct ACAutomaton
{
    int tr[N][26], fail[N], idx;
    int que[N], hh = 0, tt = -1;

    inline void insert(char *str, int id)
    {
        int cur = 0, len = strlen(str);
        for (int i = 0; i < len; i ++)
        {
            int k = str[i] - 'a';
            if (!tr[cur][k]) tr[cur][k] = ++ idx;
            cur = tr[cur][k];
        }
        rec[id] = cur;
    }

    inline void build()
    {
        hh = 0, tt = -1;
        for (int k = 0; k < 26; k ++)
            if (tr[0][k]) fail[tr[0][k]] = 0, que[++ tt] = tr[0][k];
        while (hh <= tt)
        {
            int cur = que[hh ++];
            for (int k = 0; k < 26; k ++)
            {
                if (tr[cur][k]) fail[tr[cur][k]] = tr[fail[cur]][k], que[++ tt] = tr[cur][k];
                else tr[cur][k] = tr[fail[cur]][k];
            }
        }
    
        for (int ver = 1; ver <= idx; ver ++) add(fail[ver], ver);
    }

    void query(char *str)
    {
        int cur = 0, len = strlen(str);
        for (int i = 0; i < len; i ++)
        {
            cur = tr[cur][str[i] - 'a'];
            sum[cur] ++;
        }
    }
} AC;

void dfs(int ver)
{
    for (int i = h[ver], to = e[i]; ~i; i = ne[i], to = e[i])
    {
        dfs(to);
        sum[ver] += sum[to];
    }
}

Reference

P3808 AC 自动机（简单版） - 洛谷 | 计算机科学教育新生态

P3796 AC 自动机（简单版 II） - 洛谷 | 计算机科学教育新生态

P5357 【模板】AC 自动机 - 洛谷 | 计算机科学教育新生态

AC 自动机 - OI Wiki