AC自动机

前置知识：

字典树：可以参考我的另一篇文章 算法学习笔记(15): Trie（字典树）

KMP：可以参考 KMP - Ricky2007，但是不理解KMP算法并不会对这个算法的理解产生影响。

(资料图片仅供参考)

目录AC自动机使用场景算法思想与流程匹配的判断失配树的应用对状态的理解使用场景

AC自动机是一种著名的多模式匹配算法。

可以完成类似于KMP算法的工作，但是由单字符串的匹配变成了多字符串的匹配。

一般来说，会有很多子串，和一个母串。问题常是求字串在母串中的出现情况（包括位置，次数，等等）

算法思想与流程

我在Trie树一文中提到过这样一句话

而AC自动机的核心就在于通过对Trie树进行处理，使得在处理母串的信息时可以快速的进行状态转移。

可以类比KMP的算法流程，但是这不重要

例如子串有 aa, ab, abc, b。母串为 ababcba。

由于我们是通过母串进行状态转移，所以需要先把所有字串的信息搞定

我们可以先处理子串，建一棵Trie树

明显，对于一个字串的匹配，是不可能在树上一路到底的，所以要构建匹配失败时的回退机制。也就是需要构建失配指针。

那么失配指针是干什么的？也就是用来在 Trie树上向上跳，找到可以转移的一个节点，进行状态转移。

假如我现在在3号节点，并且我下一个需要转移的状态是 b，很明显，我此时应该回退到1节点（其上第一个可以通过 b转移的节点）并转移到4节点。如果再来一个 b，也只能向上走到0号节点，然后转移到2号节点。

如此看来，我们完全可以暴力向上跳找到可转移的状态或者到达根为止。但是，这明显不够优秀，我们完全可以继承其子节点的。也就是继承 fail的子节点。使得不需要暴力向上跳。

那说了半天，fail到底指向啥？

假设父节点到当前节点转移的状态为 x，父节点之上第一个可以通过 x转移到下一个节点的节点为 u，则 fail指向 u通过 x转移过后的节点。

其实还有另一种解释的方法

fail指向 p代表当前串的最长已知后缀。

例如 aa的最长已知后缀为 a，所以 3号节点的 fail指向 1号节点；abc的最长已知后缀为空，所以 5号节点的 fail指向根节点。

好混乱，我尽力了……

那么核心代码……就是利用 BFS来处理

void procFail(int * q) {    int head(0), tail(0);    for (int i(0); i < 26; ++i) {        if (kids[0][i]) q[tail++] = kids[0][i];    }    while (head ^ tail) {        int x = q[head++];        for (int i(0); i < 26; ++i) {            if (kids[x][i]) {                fail[kids[x][i]] = kids[fail[x]][i];                q[tail++] = kids[x][i];            } else kids[x][i] = kids[fail[x]][i];        }    } // procFail end}

注意事项：一般来说，把 0号作为根节点会比较方便。反正 0上不可能有信息保存。

插入部分我就不需要讲了

匹配的判断

如何判断当前状态有没有匹配任何一个字串，只需要不断向上跳 fail，看跳到的节点是不是代表着字串。

拿模板：【模板】AC 自动机（简单版） - 洛谷 为例。

插入的时候在最后标记一下有没有匹配：

void insert(string &s) {    int p(0);    for (int c : s) {        if (!kids[p][(c -= "a")]) kids[p][c] = ++usage;        p = kids[p][c];    }    ++cnt[p];}

在匹配的时候暴力跳就是了：

int ACMatch(string & s) {    int p(0), ans(0);    for (int c : s) {        p = kids[p][(c -= "a")];        for (int t(p); t && ~cnt[t]; t = fail[t]) {            ans += cnt[t], cnt[t] = -1;        }    }    return ans;}

由于每一个串只能匹配一次，所以这里采用的清空的策略。并且标记清空，以免重复搜索。

失配树的应用

就拿模板题来说吧：【模板】AC 自动机（二次加强版） - 洛谷

他是要求所有字串的出现情况。

那么，我们先把每一个到达的状态计数。再通过 fail指针向上跳求和。

但毕竟不能每一个节点都暴力跳，所以考虑在 fail树上求和。

但是，我们不是有一个 q来 BFS吗？其中的 fail是有序的：对于一个节点 x，其 fail一定在 x之前被遍历到。

所以我们直接使用 q即可。

那么合起来大概也就是这样：

inline void ACMatch(string &s) {    int p(0);    for (char c : s) {        p = kids[p][c - "a"];        ++cnt[p];    }}inline void ACCount(int * q) {    for (int i = usage; i; --i) {        cnt[fail[q[i]]] += cnt[q[i]];    }}

但是每一个特定的字串出现的次数呢？

在插入时记住字串对应的节点，输出即可。

void insert(string &s, int i) {    int p(0);    for (int c : s) {        if (!kids[p][(c -= "a")]) kids[p][c] = newNode();        p = kids[p][c];    }    pos[i] = p;}inline void ACOutput(int n) {    for (int i = 1; i <= n; ++i) {        cout << cnt[pos[i]] << "\n";    }}

有这么一道题：

很明显，对于每一个位置，我们需要清理能匹配到的最长长度，所以我们需要预处理出最长长度：

inline void ACprepare(int * q) {    for (int i = 1; i <= usage; ++i) {        len[q[i]] = max(len[q[i]], len[fail[q[i]]]);    }}

在清理时：

inline void ACclean(string &s) {    int p(0);    for (unsigned i(0), ie = s.size(); i < ie; ++i) {        p = kids[p][discrete(s[i])];        if (len[p]) for (unsigned j = i - len[p] + 1; j <= i; ++j)            s[j] = "*";    }}

由于是引用的字符串，所以可以直接修改。

对状态的理解

在我们考试的时候有这么一道题：

这道题说难也难，说不难也不难。主要是看对于 AC自动机状态转移的理解到不到位。

在匹配过程中，如果匹配到了出现的 w，那么就要回到 len(w)个状态前，继续匹配下一个字符。

很明显，需要用栈，并且由于需要一次弹出多个，所以最好用手写的栈。

核心代码如下：

string sub, pat;cin >> sub >> pat;insert(sub), procFail(Q);int p = 0;for (int i(0), ie = pat.size(); i < ie; ++i) {    p = kids[cps[ci]][pat[i] - "a"];    cps[++ci] = p, ccs[ci] = pat[i];    if (match[p]) ci -= sub.size();}for (int i = 1; i <= ci; ++i) {    putchar(ccs[i]);}

这里没有用到 fail，那么为什么还要构建失配树？

这是个好问题，因为，构建失配树的过程不仅仅构建了失配树，同时还令节点继承了其 fail的子节点，所以需要构建的过程。

最后附上模板题【模板】AC 自动机（二次加强版） - 洛谷的代码：

#include #include #include using namespace std;const int N = 1e6 + 7;int res[N], cnt[N], pos[N];class ACAutomaton {private:int kids[N][26];int fail[N], id[N], usage;public:ACAutomaton() : usage(0) {}inline int newNode() {fill_n(kids[++usage], 26, 0);cnt[usage] = fail[usage] = id[usage] = 0;return usage;}void insert(string &s, int i) {int p(0);for (int c : s) {if (!kids[p][(c -= "a")]) kids[p][c] = newNode();p = kids[p][c];}pos[i] = p;}void procFail(int * q) {int head(0), tail(0);for (int i(0); i < 26; ++i) {if (kids[0][i])fail[kids[0][i]] = 0, q[tail++] = kids[0][i];}while (head ^ tail) {int x = q[head++];for (int i(0); i < 26; ++i) {if (kids[x][i]) {fail[kids[x][i]] = kids[fail[x]][i];q[tail++] = kids[x][i];} else kids[x][i] = kids[fail[x]][i];}} // procFail end}void debug() {for (int i = 0; i <= usage; ++i) {printf("node %d (cnt %d) fail to %d:\n\t", i, cnt[i], fail[i]);for (int j(0); j < 26; ++j) {printf("%d ", kids[i][j]);} puts("");}}inline void ACMatch(string &s) {int p(0);for (char c : s) {p = kids[p][c - "a"];++cnt[p];}}inline void ACCount(int * q) {for (int i = usage; i; --i) {cnt[fail[q[i]]] += cnt[q[i]];}}inline void ACOutput(int n) {for (int i = 1; i <= n; ++i) {cout << cnt[pos[i]] << "\n";}}void clear() {usage = -1;newNode(); // clear 0}} ac;int Q[N];string s; int main() {cin.tie(0)->sync_with_stdio(false);int n;cin >> n;for (int i = 1; i <= n; ++i) {cin >> s;ac.insert(s, i);} ac.procFail(Q);cin >> s;ac.ACMatch(s);ac.ACCount(Q);ac.ACOutput(n);return 0;}

差不多了……下课

标签：