AC 自动机学习笔记

发表于 分类于

来源

$KMP$ 算法是对于一个主串匹配一个子串，$AC$ 自动机则解决了一个主串匹配多个子串的问题。

实现

我们把子串全部建成一棵 $trie$ 树。

在匹配失败后，我们不会再跳回根节点，而是根据节点存储的 $fail$ 数组，跳到 $trie$ 上的一个点继续匹配。

失配指针（$fail$）

定义

$trie$ 上的状态 $u$ 的失配指针 $fail_u$ 指向另一个状态 $v$，满足 $v$ 是 $u$ 的最长后缀。

求法

我们令 $trie_{p,c}=u$，那么：

若 $trie_{fail_p,c}$ 存在，则 $fail_u=trie_{fail_p,c}$。

否则就往上找到 $trie_{fail_{fail_p,c}}$，判断是否存在，以此类推，直到跳到根节点，那么 $fail_u$ 就指向根节点。

显然 $fail$ 是按照深度往下遍历的，因此使用 $BFS$。

类似并查集的路径压缩，我们可以在 $trie_{u,c}$ 不存在的情况下，直接将其连接到 $trie_{fail_u,i}$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
inline void build()
{
    q.push(0);
    while (q.size()) {
        int now = q.front();
        q.pop();
        for (int i = 1; i <= 26; i++) {
            if (trie[now][i]) {
                fail[trie[now][i]] = trie[fail[now]][i];
                q.push(trie[now][i]);
            } else {
                trie[now][i] = trie[fail[now]][i];
            }
        }
    }
    return;
}

匹配

对于已经匹配到的点，我们把答案加上当前点的串的数量，同时当前点的 $fail$ 的 $fail$ 也是可以的，全部累加起来就是答案了。

可以对于每个已经遍历到的点打标记，以免重复计算。

注意有时会有重复子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
inline int query(int l, string x)
{
    int now = 0, ans = 0;

    for (int i = 0; i < l; i++) {
        now = trie[now][x[i] - 'a' + 1];
        for (int j = now; j && ex[j] != -1; j = fail[j]) {
            ans += ex[j];
            ex[j] = -1;
        }
    }
    return ans;
}

优化

在求子串出现数量时，发现暴力跳 $fail$ 极慢无比。

可以在这个点打上标记，最后从下往上累加即可。

那么如何求得累加顺序呢？

我们假设每个点都向其 $fail$ 连一条有向边。

于是就是拓扑排序。

因为 $fail$ 只有一个，每个点的出度也只有一个，就不用再开数组存边了。

入度还是要记的，这样求得起始点后就可以开始快乐 $topo$，同时累加答案。

快了好多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
inline void query(int l, string x)
{
    int now = 0;

    for (int i = 0; i < l; i++) {
        now = trie[now][x[i] - 'a' + 1];
        flag[now]++;
    }
    for (int i = 0; i <= cnt; i++)
        if (!ind[i])
            q.push(i);
    while (q.size()) {
        int now = q.front();
        q.pop();
        flag[fail[now]] += flag[now];
        ind[fail[now]]--;
        if (!ind[fail[now]])
            q.push(fail[now]);
        ans[ex[now]] = flag[now];
    }
    return;
}