AC自动机

1. 简介

AC 自动机可以看作是字典树 + KMP，其主要构建步骤为：

  • 将所有模式串插入字典树中，构建出字典树
  • BFS 字典树上所有的结点构造失配指针（同时考虑路径压缩）

AC 自动机主要应用于多模式串匹配问题，即一个主串多个匹配的模式串问题。

2. 思想

AC 自动机基于字典树结构，将所有模式串插入字典树中，然后对字典树中的每个结点构造失配指针。AC 自动机中的失配指针与 KMP 中不同的是，AC 自动机中的失配指针是相对于整棵字典树的，即失配指针不再是局限于当前模式串，而是对于整棵字典树中所有的模式串而言的。

  • AC 自动机中的失配指针匹配的是当前模式串能匹配到的最长后缀对应的字典树中的结点，即从根结点出发能够匹配到的当前字符串最长后缀的结点。

  • 假设字典树中当前结点为 uu，uu 的父结点为 pp，pp 通过边字符 cc 指向 uu，即 trie[p][c]=u trie[p][c] = u ，结点失配数组为 failfail。若深度小于 uu 的所有结点的 failfail 指针都已经求得，则：

  1. 如果结点 trie[fail[p]][c]trie[fail[p]][c] 存在，则

fail[u]=trie[fail[p]][c]\begin{array}{c} fail[u] = trie[fail[p]][c] \end{array}

  1. 如果结点 trie[fail[p]][c]trie[fail[p]][c] 不存在，则递归计算 p=fail[p]p = fail[p]，并判断结点 trie[fail[p]][c]trie[fail[p]][c] 是否存在 ⋯\cdots，直到找到或者指向根结点

fail[u]=trie[fail[p]][c]\begin{array}{c} fail[u] = trie[fail[p]][c] \end{array}

即当前结点的失配指针指向存在的最近的祖先结点的失配指针对应结点连接边字符 cc 指向的结点。

  • 由于求失配指针 failfail 数组时，要求深度小于当前结点的失配指针都已经计算出来了，所以在计算整棵字典树的 failfail 时需要使用 BFS 遍历整棵字典树。

  • 构建好 failfail 指针数组后，就可以对主串进行匹配。

  • 考虑到寻找当前结点的失配指针指向存在的最近的祖先结点的失配指针对应结点连接边字符 cc 指向的结点，这个过程可能由于 trie[fail[p]][c]trie[fail[p]][c] 不存在而导致每次匹配结点失效时都要递归查找，从而浪费了比较多的时间。实际上由于构建 failfail 指针数组时是对整棵字典树进行 BFS，因此可以对每个结点 uu 的每条出边字符 cc 计算失配指针，即对于不存在的 trie[u][c]trie[u][c] 直接指向其存在的最近的祖先结点的失配指针对应结点连接边字符 cc 指向的结点，从而使得下一次失配时如果判断到 trie[u][c]trie[u][c] 不存在，可以直接得到存在的最近的祖先结点的失配指针对应结点连接边字符 cc 指向的结点。整体思想就是类似并查集的路径压缩。

3. 模板

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
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;

#ifndef _AUTOMATON_
#define _AUTOMATON_
#define ll int
#define MAXN 2000005
#define MAXCHAR 128

// AC 自动机
struct Automaton {
    ll cnt;                 // 动态开点
    ll trie[MAXN][MAXCHAR]; // 字典树
    ll exist[MAXN];         // 字符串标记
    ll fail[MAXN];          // 失配数组
    Automaton(): cnt(0) {}
    // 插入字符串（构建字典树）
    void insert(char *str, ll n) {
        ll p = 0;
        for(ll i = 0; i < n; ++i) {
            char ch = str[i];
            if(!trie[p][ch]) {
                trie[p][ch] = ++cnt;
            }
            p = trie[p][ch];
        }
        ++exist[p];
    }
    // 构建 AC 自动机
    void build() {
        queue <ll> q;
        // BFS 遍历字典树
        for(ll i = 0; i < MAXCHAR; ++i) {
            if(trie[0][i])  q.push(trie[0][i]);
        }
        while(q.size()) {
            ll u = q.front();
            q.pop();
            for(ll i = 0; i < MAXCHAR; ++i) {
                if(trie[u][i]) {
                    fail[trie[u][i]] = trie[fail[u]][i];
                    q.push(trie[u][i]);
                } else {
                    // 路径压缩
                    trie[u][i] = trie[fail[u]][i];
                }
            }
        }
    }
    // 多模式匹配
    // 统计主串中出现的不同模式串数量
    ll query(char *str, ll n) {
        ll u = 0, res = 0;
        for(ll i = 0; i < n; ++i) {
            u = trie[u][str[i]];
            // -1 标记优化（统计过一次后就不需再次统计）
            for(ll j = u; j && ~exist[j]; j = fail[j]) {
                res += exist[j];
                exist[j] = -1;
            }
        }
        return res;
    }
};
#endif