AC自动机

$AC$ 自动机（$Aho-Corasickautomaton$）在1975年产生于贝尔实验室，是著名的多模匹配算法。

学习AC自动机之前，首先要有 $KMP$ 和 $Trie$（字典树）的基础知识。

1、构造 $Trie$ 树

我们先用 $n$ 个模式串构造一颗 $Trie$ ，$Trie$ 中的一个节点表示一个从根到当前节点的字符串。

如果节点是个模式串，打一个标记。

void insert(char* s) {
    int p = 0;
    for (int i = 0; s[i]; i ++ ) {
        int j = s[i] - 'a';
        if (!tr[p][j]) tr[p][j] = ++ idx;
        p = tr[p][j];
    }
    cnt[p] ++ ;
}
1
2
3
4
5
6
7
8
9

2、构造 $AC$ 自动机

在 $Trie$ 上构建两类边：回跳边、转移边。

• 回跳边指向父节点的回跳边所指节点的儿子。
• 转移边指向当前节点回跳边所指节点的儿子。转移边相当于 $KMP$ 的失配指针。

$ne[i]$ ：

• 存节点 $v$ 的回跳边的终点。
• 回跳边指向父节点的回跳边所指节点的儿子。
• 四个点 ($v,u,ne[u],ch[][]$) 构成四边形。
• 回跳边所指节点一定是当前节点的最长后缀。

$ch[u][i]$ ：

• 既存树边的终点也存转移边的终点。
• 三个点（$u,ne[u],ch[][]$）构成三角形。
• 转移边所指节点一定是当前节点的最短路。

用BFS构造 $AC$ 自动机：

• 初始化把根节点的儿子们入队。
• 只要队不空，节点 $u$ 出队，枚举 $u$ 的 $26$ 个儿子
  • 若儿子存在，则爹帮儿子建回跳边，并把儿子入队。
  • 若儿子不存在，则爹自建转移边。

void build() {  //创建 AC 自动机
    queue<int> q;
    for (int i = 0; i < 26; i ++ ) {
        if (tr[0][i]) q.push(tr[0][i]);
    }
    while(q.size()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < 26; i ++ ) {
            int v = tr[u][i];
            if (v) ne[v] = tr[ne[u]][i], q.push(v);
            else tr[u][i] = tr[ne[u]][i];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3、扫描主串匹配

扫描主串，依次取出字符 $s[k]$ ：

• $i$ 指针走主串对应的节点,沿着树边或转移边走,保证不回退。
• $j$ 指针沿着回跳边搜索模式串，每次从当前节点走到根节点，把当前节点中的所有后缀模式串—网打尽，保证不漏解。
• 扫描完主串,返回答案。

int query(char* s) {
    int ans = 0;
    for (int i = 0, k = 0; s[k]; k ++ ) {
        i = tr[i][s[k] - 'a'];
        for (int j = i; j && ~cnt[j]; j = ne[j]) {
            ans += cnt[j];
            cnt[j] = -1;
        }
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11

参考资料：

1、《算法训练营进阶版》— 陈小玉

2、b站董晓算法