KMP & AC 自动机

好久没写学习笔记了，反正今天讲了顺手写一下。

0. 字符串匹配

求文本串 $S$ 中有多少个子串和模式串 $T$ 相等。

很明显，我们有个 $\Omicron(|S||T|)$ 的解法，更明显的，这个算法面对 $\ge 10 ^ 4$ 的数据会 T 掉。

这个时候就该用我们的 KMP 啦。

1. 基本定义

Border：一个字符串的相等的真前后缀长度称为这个字符串的 Border，如 $AAAAA$ 的 Border 就为 $4$ 。

然后就没了。

2. KMP算法

我们发现，暴力算法慢的原因是我们会对重复的部分进行重复判定，而这个重复判定的代价高达 $\Omicron(|T|)$ 。后面判定的代价是不能减少的，所以我们只能考虑减少判定次数。

我们发现，如果发生失配，前缀和后缀相等的时候，就可以直接把前缀移到后缀匹配，减少了很多的匹配次数。

我们要匹配的次数尽量少，则移动的距离要尽量大，不难发现我们可以直接移动最长的相等前后缀长度。

KMP 就是这个思想，我们对 $S$ 的每个前缀求出最长 Border 长度，然后用这个失配指针来直接往后跳。

3.实现

由上面我们可以发现，我们需要做的就是预处理出失配后应该去哪（其实也是最长 Border 长度），记为 $next$ 。

我们可以用 DP 的方式来求这个 $next$ 。 $next _ 1$ 显然是 $0$ 。

我们设正在求解的前缀为 $[1,i]$ ，维护一个指针 $j$ ，则：

如果新加入的 $T _ i$ 与 $T _ {j + 1}$ 相等，则 $j \gets j + 1$ 。
否则，这个就相当于发生失配，直接一直跳 $next$ 直到 $j$ 归 $0$ 或 $T _ i = T _ {j + 1}$ ，然后在这里开始判断是否 $T _ i = T _ {j + 1}$ ，接着跑就行。

不难写出预处理部分的代码：

1
string S,T;
2
int kmp[MAXN],s,t;
3
inline void initKMP()
4
{
5
    s = S.length(),t = T.length();
6
    int j = 0;
7
    S = ' ' + S,T = ' ' + T;
8
    for(int i = 2;i <= t;i++)
9
    {
10
        while(j && T[j + 1] != T[i])
11
            j = kmp[j];
12
        if(T[j + 1] == T[i])
13
            ++j;
14
        kmp[i] = j;
15
    }
16
}

查询就很简单了，失配了就跳 $next$ ，指针指向末尾的就相当于找到了。

1
inline int Match()
2
{
3
    int cnt = 0;
4
    for(int i = 1;i <= s;i++)
5
    {
6
        while(j && T[j + 1] != S[i])
7
            j = kmp[j];
8
        if(T[j + 1] == S[i])
9
            ++j;
10
        if(j == t)
11
        {
12
            ++cnt;
13
            j = kmp[j];
14
        }
15
    }
16
    return cnt;
17
}

其实求 $next$ 数组的过程我觉得就是在和自己匹配。

3. AC 自动机

自动机理论太长了，贴个链接自己看看吧↗

我们先说 AC 自动机的定义，就是以 Trie 的结构 为基础，结合了 KMP 思想建立的自动机。KMP 是拿来做单模式串匹配的，AC 自动机就是拿来做多模式串匹配的。

我们需要利用 Trie 的结构，所以我们把所有模式串扔进一棵 Trie 里面。直接插入就行，同时记录一下每个字符串的结尾的结点，后面有用。

既然结合了 KMP 的思想，那 AC 自动机也应该有个失配指针。因为 Trie 树，我们已经可以维护前缀了，所以，这个失配指针指向有着最长真后缀的结点，我们之后把它叫做 $fail$ 指针。

Fail 指针的构建

我们可以再次参考 KMP 构建 $next$ 的思想，也就是算过了就不用再算一次，来构建 $fail$ ， $fail$ 指向的深度一定比自己低，所以得用 BFS 来构建。

设当前结点为 $u$ ， $v$ 是 $u$ 经过边 $c$ 的子结点，即 $\text{trie}(u,c)$ 。还是分两种情况：

$\text{trie}(fail _ u,c)$ 存在，则 $fail _ {v} = \text{trie}(fail _ u,c)$ ，相当于直接加一个字符，原来的最长真后缀还是最长真后缀。
否则，我们就一直跳 $fail$ ，直到找到一个存在的，找不到就连到根结点上。

建自动机

还没完呢，现在还只是个字典树，可能会走到底就匹配不了了，我们还需要解决这种情况。

我们可以单独开个数组 $delta$ ，表示自动机的转移函数，一般可以不单独开，但是一旦要用到原先字典树的结构就必须单独开。之后这个转移函数用数学符号，我觉得好看些。

一开始，我们初始化 $\delta(u,c) = \text{trie}(u,c)$ ，然后可以和构建 $fail$ 同时进行。我们关注 $fail$ 中不存在 $trie(fail _ u,c)$ 的情况，这个时候，我们可以为了构建 $fail$ 的方便，也为了之后转移的方便，把 $\delta(u,c)$ 设置为 $\delta(fail _ u,c)$ ，然后就没有然后了。

其实就相当于可以加字符就加字符，否则就认为失配，跳 $fail$ 。

好了构建就完成了，下面就是~~更加恶心~~的应用了。

(1) 多模匹配

前面说了，Trie 树，或者 AC 自动机上的 Trie 图，是维护前缀的，而 $fail$ 指针是维护后缀的，所以，我们可以对文本串的每个前缀，都去跳 $fail$ ，直到跳到 Trie 的根结点上，看经过了几个模式串的结尾。

但是，这么暴力的算法是包可以卡掉的，所以我们需要优化。

我们可以观察到，所有 $fail$ 指针是构成一棵内向树的，这个很好证，因为最长真后缀的深度一定小于自己，而每个结点都有最长真后缀（根结点就是空串，空串是任何非空串的最长真后缀），并且不会成环，所以一定是一棵树，之后叫做 Fail 树。

然后我们再回去看这个问题，实际上就是Trie 图上路径修改，Fail 树上子树求和，Trie 图上修改不好搞，但是我们可以优化 Fail 树上求和，子树问题可以直接上 DFS 序，然后就可以用树状数组、线段树之类的数据结构来维护了。

(2) ACAM + DP

其实很套路，一般都是设 $dp _ {i,u}$ 表示已经放了 $i$ 个字符，在 AC 自动机的结点 $u$ 上的答案，转移就是枚举下一个字符，然后走到 Trie 图上的下一个结点。

但是，有的题可以给你把这个 $i$ 开到 $10 ^ {18}$ ，并且 AC 自动机结点数不大，这个时候就可以使出传统艺能，用矩阵快速幂优化了。

(3) 合并/重构

AC 自动机本质上是个离线算法，不支持修改模式串集，但是就有这么一道毒瘤题↗，让你支持插入删除字符串，并且强制在线。

因为出现次数这个东西是有可减性的，所以我们可以维护两个 ACAM，一个只负责加字符串，一个只负责减字符串。这样就不用处理删除了（不然套个 DFS 序 + 树状数组恶心死你）。

然后我们可以采用两种办法：根号重构和二进制分组来重构 ACAM（似乎优化只能重构的一般都是这两个，KDT 也是）。

二进制分组需要合并 ACAM，就写一下合并吧。像上面讲的那样，我们字典图用 $delta$ 数组存，然后原本的 Trie 的结构就可以保存下来了，直接 Trie 树合并就行，~~反正你还得重构~~。

(4) 处理大字符集

我们发现，求 $fail$ 的过程，有很多时候都只是把不存在的儿子补完，而真正需要处理 $fail$ 的很少。

所以，我们可以用哈希表把存在的儿子记下来，然后用主席树维护出边，这样就能做到 $\Omicron(n \log |\Sigma)$ 的复杂度。

具体的，我们在 BFS 中取出一个结点的时候，把它在主席树上的根赋为它的 $fail$ 的根，然后直接单点更新已经存在的点的儿子就行了。

贴个代码，省略一个可持久化区间树模板。

1
inline void buildFail()
2
{
3
    queue<int> q;
4
    for(auto [i,v] : tree[0].son)
5
    {
6
        modify(root[0],1,V,i,v);
7
        q.emplace(v);
8
    }
9
    int u,v,Fail;
10
    while(!q.empty())
11
    {
12
        u = q.front(),Fail = tree[u].fail;
13
        q.pop();
14
        root[u] = root[Fail];
15
        for(auto [i,v] : tree[u].son)
16
        {
17
            tree[v].fail = query(root[Fail],1,V,i);
18
            modify(root[u],1,V,i,v);
19
            q.emplace(v);
20
        }
21
    }
22
}

4. 总结

某位学长说过：ACAM 分三种题：板子题，硬套题，神仙题。前两个一眼过，后面那个一眼就跳了。

AC 自动机算字符串的入门算法了，能做的还是比较有限的。

~~所以，萨菲克斯·阿瑞 & 萨菲克斯·奥托玛滕，启动！~~

Thanks for reading!

KMP & AC 自动机

2025 4月 22 周二

2212 字 · 10 分钟

算法学习笔记 OI 字符串