KMP & AC 自动机

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

0. 字符串匹配#

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

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

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

1. 基本定义#

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

然后就没了。

2. KMP算法#

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

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

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

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

3.实现#

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

string S,T;
int kmp[MAXN],s,t;
inline void initKMP()
{
    s = S.length(),t = T.length();
    int j = 0;
    S = ' ' + S,T = ' ' + T; 
    for(int i = 2;i <= t;i++)
    {
        while(j && T[j + 1] != T[i])
            j = kmp[j];
        if(T[j + 1] == T[i])
            ++j;
        kmp[i] = j;
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

inline int Match()
{
    int cnt = 0;
    for(int i = 1;i <= s;i++)
    {
        while(j && T[j + 1] != S[i])
            j = kmp[j];
        if(T[j + 1] == S[i])
            ++j;
        if(j == t)
        {
            ++cnt;
            j = kmp[j];
        }
    }
    return cnt;
}

其实求 $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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

inline void buildFail()
{
    queue<int> q;
    for(auto [i,v] : tree[0].son)
    {
        modify(root[0],1,V,i,v);
        q.emplace(v);
    }
    int u,v,Fail;
    while(!q.empty())
    {
        u = q.front(),Fail = tree[u].fail;
        q.pop();
        root[u] = root[Fail];
        for(auto [i,v] : tree[u].son)
        {
            tree[v].fail = query(root[Fail],1,V,i);
            modify(root[u],1,V,i,v);
            q.emplace(v);
        }
    }
}

4. 总结#

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

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

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