学习笔记：KMP & ACAM

wsy_I · 2026-05-31 19:54:43 · 算法·理论

KMP 和 ACAM，字符串匹配中的基本算法，很基础也很重要。CSP-S 2025 的第三题，我就算想到了正解，因为不会这俩东西只能写 O(L_1L_2) 暴力，喜提 25 分。

::::align{right} ——引言 ::::

1. KMP

1.1 理论

KMP 解决的是单模匹配问题。说人话就是给你一个模式串 s_1 和一个文本串 s_2，要求你求出 s_1 在 s_2 中出现了多少次，每一次出现在哪里。

首先考虑一个朴素的暴力。对于 s_2 的每一个位置，开始暴力匹配，也就是一个一个字符往后比对，如果找到了不同就退出，否则继续往后找。这一种方法在串随机的情况下是线性的，但是出题人可能会恶意构造数据，比如模式串是 aaaab，文本串是 aaaaaaaab，你就会发现前面的位置全都会跑满，时间复杂度变成了 O(|s_1||s_2|)。

如何优化呢？在优化之前，我们先理解一下暴力的本质，即为双指针。指针 i 指向文本串中当前匹配的位置，指针 j 指向模式串当前匹配的位置。那么暴力算法就可以做出如下的解释：让 i 从 1 到 |s_2| 递增，对于每一个 i，让 j 从 1 到 |s_1| 递增。对于 i 的递增没有什么好优化的，但是 j 一直在 1 和 |s_1| 之间反复挪动，一看就很笨的样子，考虑优化。

KMP 的思想使用图理解起来更简单，我就先放一个图吧。其中，i 指针和 j 指针前面的字符均相同，但是 i 指针和 j 指针指向的字符不同。

指向的字符不同，代表着目前这两个串不能再匹配下去了。在暴力做法中，就是将 i 挪到了字符串开头，并且将 j 向前挪了与 i 相等的长度。但是，这不是我们希望的，为了优化算法，我们希望 j 不要向前挪动。那么 i 指针该往哪里跳呢？

在 s_1 的开头，必定有一段字符，和 i 前面的字符相同，并且这被叫做公共前后缀。最长的公共前后缀就叫最长公共前后缀（废话），最长公共前后缀可以为空，但是不能等于 1\sim i 这个串。此时 j 前面的和 i 前面的若干位必定相同，所以 i 往前移动需要保持 i 前面是什么不变，不就是要往前面的最长公共前后缀的结尾跳吗？比如说下面，蓝色线条为最长公共前后缀。

就会变成这样：

发现现在 i 和 j 前面的字符还是相同的，但是，i 指向的字符变了，这意味着 i 可能可以和 j 一起向后挪一位。假如不可以，指向的字符还是不相同，那就往最长公共前后缀再跳一步，一直跳到前后缀为空串（i 指向开头）或者可以匹配了。然后 i, j 一起往后挪一位。

发现我们刚才巧妙的使用最长公共前后缀避免了 j 指针回溯！但是，问题是对于每一个前缀最长公共前后缀你怎么求啊。其实这个很好求的，可以使用一个巧妙的递推。我们把这个串也使用双指针扫描（有些人说是自己和自己做匹配，但是我并不这么认为），让 i 指向最长公共前后缀末尾的位置，让 j 指向当前需要推出最长公共前后缀的位置。假如指向的字符相同，那么都往后挪一位，否则就像匹配一样一直往前跳（注意到 i<j，所以前面的最长公共前后缀都一定是被求出来了的），直到两个字符相同，然后往后挪一位。

根据定义，对于前缀 1\sim j 的最长公共前后缀长度（或者结尾位置）就是这个 j 和 i 匹配时 i 的位置。于是最长公共前后缀是容易求出的。时间复杂度是 O(|s_1|+|s_2|) 的。证明是容易的：j 只会顺序扫，所以 j 增加 |s_2| 次，每一次 i, j 都是一起增加的，所以 i 增加 |s_2| 次。每一次向前跳都至少会跳一个字符，所以往前也最多跳 |s_2| 次。对于匹配就是 O(|s_2|) 的，预处理最长公共前后缀就是 O(|s_1|) 的。

1.2 代码

使用模板题给出代码。

你发现还要求一个 border，这是什么东西？其实就是最长公共前后缀。所以直接在预处理完最长公共前后缀之后输出就可以了（这是模板题你希望它搞出什么高深的东西）。代码如下：

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 1e6 + 5;
int nxt[N];
string s1, s2;

void getnext() { //计算最长公共前后缀
    int j = 0;
    for(int i = 2; i < s2.size(); i ++ ) { //第一个的最长公共前后缀肯定是 0，所以从 2 开始
        while(j && s2[j + 1] != s2[i]) j = nxt[j]; //往前一直跳到匹配成功
        if(s2[j + 1] == s2[i]) j ++ ; //如果匹配成功而不是空串就将 j 往后挪一位
        nxt[i] = j; //按照定义记录
    }
}

void KMP() {
    int j = 0;
    for(int i = 1; i < s1.size(); i ++ ) {
        while(j && s2[j + 1] != s1[i]) j = nxt[j]; //和求最长公共前后缀差不多，不做解释
        if(s2[j + 1] == s1[i]) j ++ ;
        if(j == s2.size() - 1) { //如果 j 指到了串末尾，表明形成了匹配
            cout << i - j + 1 << endl;
            j = nxt[j];
        }
    }
}

int main() {
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> s1 >> s2;
    s1 = " " + s1, s2 = " " + s2; //转成 1-based 我自认为更好写一些
    getnext();
    KMP();
    for(int i = 1; i < s2.size(); i ++ ) cout << nxt[i] << " "; //最后还要输出最长公共前后缀
    return 0; 
} 

1.3 例题

1.3.1 无线传输

答案是串长度减去最长公共前后缀长度。我认为这是一道很好的题目，虽然答案我瞎猜也能猜出来，重点在于答案为什么是这个的分析。我们将这个串拆开成两个串，其中一个是前缀一个是后缀，可以更加便于理解。首先，我们对于前缀分段，长度即为原串减去后缀：

由两个串本来是一样的，所以我们可以得到 1 和 2 所代表的串是相同的。由于是公共前后缀，所以 2 和 3 代表的是相同的。然后由于位置一样，就可以推出 3 和 4 是相同的……以此类推，1, 3, 5, 7 全部相同，所以原串减去最长后缀就是一个合法的循环节。相似的，原串减去最长前缀也是一个合法的循环节。同样的，由于这是最长公共前后缀，所以循环节并不能够变短（否则这就不是最长公共前后缀了，可以反证），于是这道题就迎刃而解了。时间复杂度显然 O(L)。

::::success[code] 很短，也很巧妙。

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 1e6 + 5;
int L, nxt[N];
string s;

void getnext() {
    int j = 0;
    for(int i = 2; i <= L; i ++ ) {
        while(j && s[j + 1] != s[i]) j = nxt[j];
        if(s[j + 1] == s[i]) j ++ ;
        nxt[i] = j;
    }
}

int main() {
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> L >> s;
    s = " " + s;
    getnext();
    cout << L - nxt[L] << endl;
    return 0; 
} 

::::

1.3.2 Milking Grid

上一道题拓展到二维上的情况。容易想到这个肯定是由一个循环的矩形铺出来的。

注意到我们可以把每一行看做一个点，把每一列看做一个点，分别使用上一题的方法求出最短循环节，然后把答案乘起来就可以了。证明也类似上一道题，可以由左上角的矩形推出来分割得到的每一个矩形都相等于这个矩形。如何判断每一行是否相等？由于这里 r 和 c 很小，所以暴力也可以，但是我更喜欢字符串哈希。此处 KMP 不是主要复杂度，求哈希和输入才是主要复杂度，时间复杂度 O(rc)。

::::success[code]

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ull = unsigned long long;

const int N = 1e4 + 5, P = 131, M = 75;
int r, c, a, b, nxt[N];
char mp[N][80];
ull lhsh[N], chsh[N];

int KMP(ull a[], int n) {
    int j = 0;
    for(int i = 2; i <= n; i ++ ) {
        while(j && a[j + 1] != a[i]) j = nxt[j];
        if(a[j + 1] == a[i]) j ++ ;
        nxt[i] = j;
    }
    return n - nxt[n];
}

int main() {
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> r >> c;
    for(int i = 1; i <= r; i ++ ) 
        for(int j = 1; j <= c; j ++ ) cin >> mp[i][j];
    for(int i = 1; i <= r; i ++ ) {
        ull v = 0;
        for(int j = 1; j <= c; j ++ ) v = v * P + mp[i][j] + M;
        lhsh[i] = v;
    }
    a = KMP(lhsh, r);
    for(int i = 1; i <= c; i ++ ) {
        ull v = 0;
        for(int j = 1; j <= r; j ++ ) v = v * P + mp[j][i] + M;
        chsh[i] = v; 
    }
    b = KMP(chsh, c);
    cout << a * b << endl;
    return 0; 
} 

::::

1.3.3 动物园

一道很好的题，可以帮助理解 KMP 的本质。首先，有一个很显著的暴力，就是对于匹配的时候，暴力向前跳最长公共前后缀，假如长度小于等于当前位置的一半就记录答案。但是，这个暴力是假的，因为最长公共前后缀可能是只会向前挪动一格的，那么对于每一个点向前跳，时间复杂度就是 O(n^2) 的，假掉了。给你 10^6 个 a 就可以卡掉。

那么该如何优化？此时就来到 KMP 的本质了。假如每一个节点和它最长公共前后缀中前缀结尾的点连一条边的话，就会形成一棵树（空串视为 0 号节点，也是树根）。这一点是显然的，因为最长公共前后缀的长度必然小于这一个节点的编号。于是，从每一个节点暴力往前跳，就可以被转化为从这个节点开始，找到在到根的路径上第一个小于等于标号一半的点。这一步显然可以树上倍增。这一个点再往前直到根都是合法的答案，所以要求的就是这一个点的深度。

注意计算深度的时候不能简单粗暴的把最后一个合法点的深度减一，因为可能本来最长公共前后缀就是合法的，这样你就会多减去一个，导致答案偏小。还有，空串不应该计入答案，所以根节点的深度为 0 而不是 1。还有，倍增要精细实现，假如 TLE 了可以考虑交换两维。

::::success[code]

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ull = unsigned long long;

const int N = 1e6 + 5;
const int MOD = 1e9 + 7;
vector<int> t[N]; 
int T, nxt[N], num[N], l, dep[N], go[22][N], lg2[N];
string s;

void dfs(int u, int fa) {
    if(u) dep[u] = dep[fa] + 1; 
    for(auto v : t[u]) {
        if(v == fa) continue;
        go[0][v] = u;
        dfs(v, u);
    }
}

void KMP() {
    int j = 0;
    for(int i = 0; i <= l; i ++ ) t[i].clear();
    for(int i = 2; i <= l; i ++ ) {
        while(j && s[j + 1] != s[i]) j = nxt[j];
        if(s[j + 1] == s[i]) j ++ ;
        nxt[i] = j;
    }
    for(int i = 1; i <= l; i ++ ) {
        t[nxt[i]].push_back(i);
        t[i].push_back(nxt[i]);
    }
    dfs(0, 0);
    for(int i = 2; i <= l; i ++ ) lg2[i] = lg2[i / 2] + 1;
    for(int i = 1; i <= lg2[l]; i ++ )
        for(int j = 1; j <= l; j ++ )
            go[i][j] = go[i - 1][go[i - 1][j]];
    for(int i = 2; i <= l; i ++ ) {
        int tj = nxt[i];
        if(tj * 2 > i) {
            for(int j = lg2[l]; j >= 0; j -- )
                if(go[j][tj] * 2 > i) tj = go[j][tj];
            tj = go[0][tj];
        }
        num[i] = dep[tj];
    }
}

int main() {
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> T;
    while(T -- ) {
        cin >> s;
        s = " " + s;
        l = s.size() - 1;
        KMP();
        int ans = 1;
        for(int i = 1; i <= l; i ++ ) ans = 1ll * ans * (num[i] + 1) % MOD;
        cout << ans << endl;
    }
    return 0; 
} 

::::

1.3.4 其它练习题

• OKR-Periods of Words
• 最长前缀
• 第一首歌
• 串串题
• 符文破译
• Binary String

2. ACAM

2.1 理论

ACAM（即 AC 自动机），用于解决字符串的多模匹配问题。即给定一个文本串（t）和多个模式串（s_1, s_2, \ldots, s_n），求出现过多少个模式串，或者每一个模式串出现过多少次。前者比较简单，后者则需要拓扑排序优化。在学习 ACAM 之前，请确保你会 Trie 和 KMP。

由于前者比较简单，所以在本部分将会讲解前者而不是后者。假设给出文本串 aabcd，我们需要判断 aa，ab，bc 是否出现过。暴力做法就是对于每一个串跑一遍 KMP，但是这显然太慢了，所以我们考虑将字符串打包成一个 Trie 批量处理。为什么要选择 Trie？我们回顾 KMP 的匹配思想，就是找到下一个合法的字符，也就是前缀相同。由于 Trie 就天生支持前缀匹配，所以必然是 ACAM 的基础。

把这些串扔上一个 Trie（没错，就是普通的 Trie）就长这样：

然后我们认真想想怎么匹配。到了一个节点，我们已经确保了前缀都是全部相同的，所以新的一个节点就直接在 Trie 上往下找就可以了。但是，假如不存在那个节点怎么办？比如我们匹配到 aab 的时候，此时我们在的节点不存在 b 这个孩子，该如何继续匹配？并且，假如我们匹配到了 aa 这个字符串，到底该如何处理贡献？

这个时候，我们就需要引入两个新的概念了：失配指针和虚儿子。这个失配指针，表示在某一个节点假如匹配成功，应该到哪里去贡献。（不是，所以为什么叫失配指针啊）该到哪里去呢？显然就是到满足是它的一个后缀，且深度最大的节点去。假如没有，那么就指向根。对于上图，可以构造出失配指针如下：

例如我们匹配了 aa，目前在 aa 这个节点。那么，就会对于 aa，a 这两个串有贡献（串肯定是在 AC 自动机中的），所以就直接寻找有哪些串是 aa，哪些串是 a，然后累加结果即可。为了优化复杂度，我们可以对于一个节点打一个访问标记，表示这一个节点到根的失配指针构成的链都已经贡献过了，这样每一个节点最多会被访问一次，就是 O(\sum |s_i|) 的了。

至于虚儿子，则是匹配不了的时候该跳转到哪里。例如匹配到 aab，我们发现 aa 此时没有办法向下走了。

那么我们可以让 aa 这个字符串的 b 儿子直接对应到 aab 的最长在 ACAM 上的后缀，在本例里是 ab。那么，这样遇到不能匹配的情况的时候，还是可以直接通过跳转儿子来得到应该到的位置。虽然有人说这也算失配指针，但是我认为这个和失配指针有本质区别。

但是，这两个东西怎么求啊？其实很简单，可以使用 bfs 配合递推思想。首先，根由于没有后缀了，所以失配指针肯定指向自己，所有的虚儿子也指向自己。由于全局数组初始化为 0，所以我们令根为 0 会方便很多。然后呢，根的所有儿子的失配指针和虚儿子都指向根，这一点也很显然。

然后，我们考虑如何从一个节点的父亲递推到这一个节点。注意，由于父亲的所有信息都要被求出，并且其失配指针也要被求出，所以深度小于这个节点的所有节点都应该处理完毕，也就是 bfs 的顺序。首先，这一个节点的失配指针应该指向哪里？首先，它父亲的失配指针已经被求出，所以它父亲的失配指针就是父亲对应的最长后缀。它的失配指针应该指向哪里呢？就是它父亲失配指针的这个儿子。容易发现不管这个儿子是不是虚儿子这样指都是最优的。

虚儿子又应该指向哪里呢？某个字符串的失配指针已经求出来了的话，那么它的虚儿子也应该是失配指针的那个儿子，因为虚儿子是最长后缀，这与失配指针定义恰好相同。所以说，虚儿子和实儿子的失配指针指向的其实是同一个东西……

具体代码实现的时候可以在处理这个节点的时候计算它的虚儿子和实儿子的失配指针，这样会好写一点。看代码吧：

queue<int> q;
void get_fail() {
    t[0].fail = 0; //根节点失配指针指向自己，可以不写
    for(int i = 0; i < 26; i ++ ) {
        if(t[0].ch[i]) {
            t[t[0].ch[i]].fail = 0; //第一层失配指针指向根节点，可以不写
            q.push(t[0].ch[i]); //节点入队
        }
    }
    while(!q.empty()) { //bfs
        int u = q.front(); q.pop();
        for(int i = 0; i < 26; i ++ ) { //检查所有儿子
            int v = t[u].ch[i];
            if(v) { //如果是实儿子
                t[v].fail = t[t[u].fail].ch[i]; //计算失配指针
                q.push(v); //入队
            }
            else t[u].ch[i] = t[t[u].fail].ch[i]; //虚儿子
        }
    }
}

查询是容易的，之前已经讲过了。直接放代码：

void AutoAC() {
    int u = 0; //从根开始
    for(int i = 0; i < T.size(); i ++ ) {
        int v = t[u].ch[T[i] - 'a'];
        while(v && t[v].cnt != -1) { //对于失配指针链上的节点贡献
            ans += t[v].cnt; //累加贡献
            t[v].cnt = -1; //打标记
            v = t[v].fail; //跳转指针
        }
        u = t[u].ch[T[i] - 'a']; //往儿子走
    }
}

2.2 代码

模板题的完整实现。由于每一个节点最多被访问一次，所以匹配不是主要时间复杂度，失配指针的构建才是主要复杂度，为 O(n\varSigma)，其中 \varSigma 表示字符集大小，n 表示模式串总长，\varSigma 一般为常数，比如这道题就是 26。

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 1e6 + 5;
struct Node { int ch[26], cnt, fail; } t[N]; //孩子，贡献个数，失配指针
int cnt = 0, n, ans = 0;
string s, T;

void insert(string s) { //建立初始字典树
    int u = 0;
    for(int i = 0; i < s.size(); i ++ ) {
        int c = s[i] - 'a';
        if(!t[u].ch[c]) t[u].ch[c] = ++ cnt;
        u = t[u].ch[c];
    }
    t[u].cnt ++ ;
}

queue<int> q;
void get_fail() {
    t[0].fail = 0;
    for(int i = 0; i < 26; i ++ ) {
        if(t[0].ch[i]) {
            t[t[0].ch[i]].fail = 0;
            q.push(t[0].ch[i]);
        }
    }
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(int i = 0; i < 26; i ++ ) {
            int v = t[u].ch[i];
            if(v) {
                t[v].fail = t[t[u].fail].ch[i];
                q.push(v);
            }
            else t[u].ch[i] = t[t[u].fail].ch[i];
        }
    }
}

void AutoAC() {
    int u = 0;
    for(int i = 0; i < T.size(); i ++ ) {
        int v = t[u].ch[T[i] - 'a'];
        while(v && t[v].cnt != -1) {
            ans += t[v].cnt;
            t[v].cnt = -1;
            v = t[v].fail;
        }
        u = t[u].ch[T[i] - 'a'];
    }
}

int main() {
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> s, insert(s);
    get_fail();
    cin >> T;
    AutoAC();
    cout << ans << endl;
    return 0;
} 

2.3 例题

2.3.1 AC 自动机（简单版 II）

跟上一题差不多的 AC 自动机。本题显然可以求出每一个模式串的出现次数注意到题目保证不存在两个不相同的模式串，所以字典树的每一个节点最多对应一个模式串的结尾。于是可以记录每一个节点代表模式串的结尾，每一次暴力跳失配指针。注意到这一题并不能够使用标记，因为一个节点是可以多次贡献的。

由于暴力跳失配指针每一次至少上升 1 的深度，所以时间复杂度是 O(L_1) 的，L_1 表示字典树深度或者模式串的最大长度。一共会更新 L_2 次，L_2 表示文本串长度。所以时间复杂度是 O(L_1L_2) 的，可以通过本题，没有办法过真正的 ACAM 模板。注意多测一定要清空。

::::success[code]

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 1e6 + 5;
int n, ans[155], cnt;
string s[155], T;
struct Node {
    int ch[26], fail, end;
} t[20005];

void insert(int num, string s) {
    int u = 0;
    for(int i = 0; i < s.size(); i ++ ) {
        int c = s[i] - 'a';
        if(!t[u].ch[c]) t[u].ch[c] = ++ cnt;
        u = t[u].ch[c];
    }
    t[u].end = num;
}

queue<int> q;
void get_fail() {
    for(int i = 0; i < 26; i ++ ) {
        if(t[0].ch[i]) {
            q.push(t[0].ch[i]);
            t[t[0].ch[i]].fail = 0;
        }
    }
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = 0; i < 26; i ++ ) {
            int v = t[u].ch[i];
            if(v) {
                t[v].fail = t[t[u].fail].ch[i];
                q.push(v); 
            }
            else t[u].ch[i] = t[t[u].fail].ch[i];
        }
    }
}

void AutoAC() {
    int u = 0;
    for(int i = 0; i < T.size(); i ++ ) {
        int v = t[u].ch[T[i] - 'a'];
        for(; v; v = t[v].fail)
            ans[t[v].end] ++ ;
        u = t[u].ch[T[i] - 'a'];
    }
}

void clear() {
    memset(t, 0, sizeof t);
    memset(ans, 0, sizeof ans);
    cnt = 0;
}

int main() {
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    while(1) {
        clear();
        cin >> n;
        if(n == 0) break;
        for(int i = 1; i <= n; i ++ ) {
            cin >> s[i];
            insert(i, s[i]);
        }
        get_fail();
        cin >> T;
        AutoAC();
        int mx = 0;
        for(int i = 1; i <= n; i ++ ) mx = max(mx, ans[i]);
        cout << mx << endl;
        for(int i = 1; i <= n; i ++ )
            if(ans[i] == mx) cout << s[i] << endl;
    }
    return 0;
} 

::::

2.3.2 【模板】AC 自动机

这才是 AC 自动机的完全体！首先，模式串可以重复，所以呢，可以使用哈希判重，就避免了对于 ACAM 上每一个节点都是用一个 vector 存储，节省了空间，并且使得最后统计答案方便许多。

然后呢，就是 ACAM 一个很重要的技巧了：拓扑优化！注意到 ACAM 的失配指针构成一棵树，所以我们每一次修改到根的时候都只需要在需要修改节点上打一个标记，最后再一遍拓扑排序（或者也可以把这棵树建出来然后跑 dfs）就可以求出来每一个节点子树中的和了，这个和就是这个节点被贡献的次数。

具体实现并不复杂，就是一个拓扑排序。由于之前计算的时候每一次只打了一个标记，所以时间复杂度是 O(L_2) 的。那么此时主要时间复杂度就来到建立 ACAM 了，为 O(n\varSigma)。代码实现其实也并不复杂：

::::success[code]

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ull = unsigned long long;

const int N = 2e5 + 5, P = 131, M = 75;
unordered_map<ull, int> ans;
unordered_map<ull, bool> vis;
int n, cnt = 0, in[N];
ull hsh[N];
struct Node { int ch[26], fail, ans, end; } t[N];
string s, T;

ull get_hash(string s) { //字符串哈希
    ull h = 0;
    for(int i = 0; i < s.size(); i ++ ) h = h * P + M + s[i];
    return h;
}

void insert(int num, string s) {
    int u = 0;
    for(int i = 0; i < s.size(); i ++ ) {
        int c = s[i] - 'a';
        if(!t[u].ch[c]) t[u].ch[c] = ++ cnt;
        u = t[u].ch[c];
    }
    t[u].end = num;
}

queue<int> q;
void get_fail() { //建立 ACAM
    for(int i = 0; i < 26; i ++ ) {
        if(t[0].ch[i]) {
            t[t[0].ch[i]].fail = 0;
            in[0] ++ ;
            q.push(t[0].ch[i]);
        }
    }
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(int i = 0; i < 26; i ++ ) {
            int v = t[u].ch[i];
            if(v) {
                t[v].fail = t[t[u].fail].ch[i];
                in[t[t[u].fail].ch[i]] ++ ;
                q.push(v);
            } else {
                t[u].ch[i] = t[t[u].fail].ch[i];
            }
        }
    }
}

void AutoAC() {
    int u = 0;
    for(int i = 0; i < T.size(); i ++ ) {
        int v = t[u].ch[T[i] - 'a'];
        t[v].ans ++ ; //打一个标记
        u = v;
    }
}

void topo() { //拓扑排序
    for(int i = 1; i <= cnt; i ++ ) if(in[i] == 0) q.push(i);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        int v = t[u].fail;
        t[v].ans += t[u].ans; //直接累加就可以了
        in[v] -- ;
        if(in[v] == 0) q.push(v);
    }
    for(int i = 1; i <= cnt; i ++ )
        if(t[i].end) ans[hsh[t[i].end]] += t[i].ans; //统计答案
}

int main() {
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++ ) {
        cin >> s;
        hsh[i] = get_hash(s);
        if(!vis[hsh[i]]) {
            vis[hsh[i]] = true;
            insert(i, s); //只插入没有重复的串
        }
    }
    get_fail();
    cin >> T;
    AutoAC();
    topo();
    for(int i = 1; i <= n; i ++ ) cout << ans[hsh[i]] << endl; 
    return 0;
} 

::::

2.3.3 谐音替换

从哪里跌倒，就从哪里站起来。其实你会 ACAM 了之后这道题其实很简单的。

考虑如何刻画一个 t_1\to t_2 的变换。首先，它们的最长公共前后缀不应该被修改，直接塞到文本串的最前面和最后面。然后呢，去除掉最长公共前后缀的 t_1 和 t_2 就直接塞到文本串里，两边打上一个特殊字符作为标记。我选择使用 {，因为 { 的 ASCII 码值比 z 恰好大 1。比如说，对于 abc 和 adc，构造出来的文本串就是 a{bd{c。

对于 s_1\to s_2 进行相同的构造。然后问题就被转换成了一个多模匹配问题，直接跑 ACAM 即可。为什么这样做是对的？我们使用 { 包含的字符串就是有效的修改，如果 { 里面的串长度不一样或者有位置不一样都不能形成匹配。{ 外面的就相当于消除掉前后缀的影响，但是假如修改串的前后缀不正确也无法修改，这一部分也在匹配中做完了。emmm，是一个非常巧妙的转化，我场上都想出来了！

注意到这道题的 n 非常大，竟然到了 5\times 10^{6}，所以我们的 ACAM 需要精细卡常才能够通过。由于这里只需要判断串是否出现过，所以直接用标记就可以了，做法和最开始那道题一样。至于清空，记录上一次修改的所有东西，最后再重置回来就可以了。

::::success[code]

#include <iostream>
#include <string>
using namespace std;

const int N = 5e6 + 5;
char s1[N], s2[N], t1[N], t2[N];
int ch[N][27], fail[N], cnt[N], q[N], hh, tt, fi[N], se[N];
int n, Q, tot, node_cnt, ans;

string work(string &s1, string &s2) {
    string fr, bk, md1, md2;
    int bp;
    int len = s1.size();
    for(int i = 0; i < len; i ++ ) {
        if (s1[i] == s2[i]) fr += s1[i];
        else break;
    }
    for(int i = len - 1; i >= 0; i -- ) {
        if (s1[i] != s2[i]) {
            bp = i + 1;
            break;
        }
    }
    for(int i = bp; i < len; i ++ ) bk += s1[i];
    int fr_len = fr.size(), bk_len = bk.size();
    for(int i = fr_len; i < len - bk_len; i ++ ) md1 += s1[i];
    for(int i = fr_len; i < len - bk_len; i ++ ) md2 += s2[i];
    return fr + "{" + md1 + md2 + "{" + bk;
}

void insert(string &s) {
    int u = 0;
    int len = s.size();
    for(int i = 0; i < len; i ++ ) {
        int c = s[i] - 'a';
        if (!ch[u][c]) ch[u][c] = ++ node_cnt;
        u = ch[u][c];
    }
    cnt[u] ++ ;
}

void get_fail() {
    hh = 0, tt = -1;
    for(int i = 0; i < 27; i ++ ) {
        if(ch[0][i]) {
            q[ ++ tt] = ch[0][i];
            fail[ch[0][i]] = 0;
        }
    }
    while(hh <= tt) {
        int u = q[hh ++ ];
        for(int i = 0; i < 27; i ++ ) {
            int v = ch[u][i];
            if(v) {
                fail[v] = ch[fail[u]][i];
                q[ ++ tt] = v;
            } 
            else ch[u][i] = ch[fail[u]][i];
        }
    }
}

void AutoAC(string &T) {
    ans = 0;
    while(tot) {
        cnt[fi[tot]] = se[tot];
        tot -- ;
    }
    int u = 0;
    int len = T.size();
    for(int i = 0; i < len; i ++ ) {
        u = ch[u][T[i] - 'a'];
        for (int v = u; v && cnt[v] != -1; v = fail[v]) {
            ans += cnt[v];
            fi[ ++ tot] = v;
            se[tot] = cnt[v];
            cnt[v] = -1;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> Q;
    for(int i = 1; i <= n; i ++ ) {
        string a, b;
        cin >> a >> b;
        string str = work(a, b);
        insert(str);
    }
    get_fail();
    while(Q -- ) {
        string a, b;
        cin >> a >> b;
        if (a.size() != b.size()) {
            cout << "0\n";
            continue;
        }
        string str = work(a, b);
        AutoAC(str);
        cout << ans << '\n';
    }
    return 0;
}

::::

2.3.4 Video Game G

这道题涉及字符串的匹配，虽然并不是一个标准的多模匹配问题，但是我们还是考虑 ACAM。建立出 ACAM 之后，我们考虑要求的这个字符串本质是什么。

首先定义一个节点的点权为走到这个节点之后可以通过跳失配指针到达的点表示的字符串结尾数之和，这一个先让可以在求失配指针的时候顺带推出。那么问题可以转化为：给你一个有向图，只能沿着边移动，求一条长度为 k 的路径使得经过的点点权之和最大。

这是一个简单的图上 DP。首先设 dp_{i,u} 表示走 i 步之后来到 u 号节点产生的最大点权和。初始化数组为 -\infin，设 dp_{0,0}=0，直接枚举每一条边转移即可。我代码具体实现的时候使用了滚动数组滚掉了 i 这一维。

::::success[code]

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 3e2 + 5;
int n, k, cnt = 0, dp[2][N];
vector<pair<int, int> > w;
queue<int> q;
struct Node { int ch[3], fail, cnt; } t[N];
string s;

void insert(string s) {
    int u = 0;
    for(int i = 0; i < s.size(); i ++ ) {
        int k = s[i] - 'A';
        if(!t[u].ch[k]) t[u].ch[k] = ++ cnt;
        u = t[u].ch[k];
    }
    t[u].cnt ++ ;
}

void get_fail() {
    for(int i = 0; i < 3; i ++ )
        if(t[0].ch[i]) q.push(t[0].ch[i]);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(int i = 0; i < 3; i ++ ) {
            int v = t[u].ch[i];
            if(v) {
                t[v].fail = t[t[u].fail].ch[i];
                t[v].cnt += t[t[v].fail].cnt;
                q.push(v);
            }
            else t[u].ch[i] = t[t[u].fail].ch[i];
        } 
    }
    for(int i = 0; i <= cnt; i ++ )
        for(int j = 0; j < 3; j ++ ) w.push_back(make_pair(i, t[i].ch[j]));
}

int main() {
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i ++ ) cin >> s, insert(s);
    get_fail();
    memset(dp[0], -0x3f, sizeof dp[0]);
    dp[0][0] = 0;
    for(int i = 1; i <= k; i ++ ) {
        memset(dp[1], -0x3f, sizeof dp[1]);
        for(auto [u, v] : w) dp[1][v] = max(dp[1][v], dp[0][u] + t[v].cnt);
        swap(dp[0], dp[1]);
    }
    int ans = 0;
    for(int i = 0; i <= cnt; i ++ ) ans = max(ans, dp[0][i]);
    cout << ans << endl; 
    return 0;
} 
::::

## 2.3.5 其它练习题

难度按照个人主观升序排序。

- [单词](https://www.luogu.com.cn/problem/P3966)
- [Sensoring G](https://www.luogu.com.cn/problem/P3121)
- [通配符匹配](https://www.luogu.com.cn/problem/P3167)
- [病毒](https://www.luogu.com.cn/problem/P2444)
- [数数](https://www.luogu.com.cn/problem/P3311)
- [Critical Misread](https://www.luogu.com.cn/problem/AT_abc458_f)
- [Divljak](https://www.luogu.com.cn/problem/P5840)