2026年4月专项训练巩固总结

KMP

给你一个字符串 s，不妨下标从 1 到 n。

考虑 kmp 算法，ne[i] 表示对于 s[1...i] 来说，最长的非平凡后缀 = 非平凡前缀的长度。具体来说，是最大的 len，满足 s[1...len] = s[i - len + 1...i]。

如何快速求 ne[i]？

首先，ne[0] = ne[1] = 0 是显然的。

然后，我们假设 ne[0] 到 ne[i - 1] 都求出来了，现在想求 ne[i]。

我们其实就是想找最大的一段前缀 s[1...pre]，使得这个前缀和 s[1...i - 1] 的某个后缀相等，且这个前缀的下一个字符 s[pre + 1] 刚好等于 s[i]，就可以充分利用之前的最长结果求出现在的 ne[i]。

根据上面的指导思想，我们先保证前缀和后缀相等，故自然地令 j = ne[i - 1]，则 s[1...j] = s[i - j...i - 1] 就成立了。接下来，就是看下一个字符是否相等了。

如果 s[j + 1] = s[i]，则正好可以继续延续上面的相等，使得 s[1...j + 1] = s[i - j...i]，ne[i] = j + 1 即可了。

如果 s[j + 1] != s[i]，我们让 j = ne[j]，继续往前配就好了，直到 j 变为 0。

这样就求出了 ne 数组。

假设我们求出了模式串 s 的 ne 数组，现在想求文本串 t 中出现了多少次 s，如何做？

这里仍然是假设都是 1 下标开始。

那么 i = 1, j = 0，i 是 t 当前的字符，j 就是 i 之前（不包括 i）的字符匹配到的地方。

我们当然是关心 s[j + 1] 和 t[i] 是否相等。

如果相等，那么说明又匹配上了一个字符， j++，如果 j 到末尾了说明匹配成功了一次。

如果不相等，还是 j = ne[j] 去往前跳。

根据上述思想，非常容易能写出下面的代码，都是下标为 1 开始的：

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m;
    string p, s;
    cin >> n >> p >> m >> s;
    s = " " + s;
    p = " " + p;
    vector<int> ne(n + 2, 0);
    for (int i = 2; i <= n; i++) {
        int j = ne[i - 1];
        while (j && p[j + 1] != p[i]) {
            j = ne[j];
        }
        
        if (p[j + 1] == p[i]) {
            ne[i] = j + 1;
        }
    }
    
    int j = 0;
    for (int i = 1; i <= m; i++) {
        while (j && s[i] != p[j + 1]) {
            j = ne[j];
        }
        
        if (s[i] == p[j + 1]) {
            j++;
        }
        
        if (j == n) {
            cout << i - j << " ";
        }
    }
    
    return 0;
}

AC自动机

前面的 kmp 是一个复习（其实之前也不咋会），现在我们来看 AC 自动机，这玩意就是把 kmp 的失配后往回跳的 ne 数组搬到了 trie 树上，改了个名字叫 fail 数组。

考虑有 n 个字符串，建立一棵 trie 树，在 trie 上对每个结点求一个 fail。trie 从根到某个结点 p 构成一个字符串 s，对这个结点求 fail，其实就是看这个 s 的最长的真后缀，其是这 n 个字符串里某个字符串的真前缀，fail[p] 就是指向这个真前缀的结点。

可以注意到，fail 指针都是从 trie 的深处往浅处连的，所以只看 fail 指针的话，是一个有向无环图。

在 trie 建好之后，如何求 fail 呢？

这个过程类似 kmp 求 ne 数组。假如要求 p 的某个孩子结点 son 的 fail 指针，且 son 是在 p 后加了一个 ch 字符，则首先我们也是让 j = fail[p]，然后看 j 结点往 ch 方向走有没有结点，有的话相当于匹配上了，fail[son] = tr[j][ch] 即可了；如果没匹配上，则得继续 j = fail[j] 往上跳，直到跳到 0 或者匹配上了。

我们注意到，在求 fail[son] 时要求比 son 浅的结点的 fail 指针都求出来了，不然没法一直往上跳，所以我们可以以 BFS 序去求 fail 指针，这样就可以保证这一点。

如何跑匹配呢？也是类似 kmp，配不上就往上跳 fail，配上了就跑到了 trie 的一个结点上，进一步统计信息的话，可能你还需要继续往上跳 fail，才能把该统计的信息统计全。

const int N = 1e6 + 10;

struct ACAM {
    int tr[N][26];
    int cnt[N], fail[N];
    int idx;

    void init(int sz) {
        memset(tr, 0, sizeof tr);
        memset(cnt, 0, sizeof cnt);
        memset(fail, 0, sizeof fail);
        idx = 0; // 我们假设 0 是根节点，并认为 0 也是完全配不上的 fail 指针的初值
    }

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

    // 做 bfs，求 fail 指针
    void get_fail() {
        queue<int> q;
        for (int ch = 0; ch < 26; ch++) {
            if (tr[0][ch]) {
                q.push(tr[0][ch]);
            }
        }

        while (!q.empty()) {
            int p = q.front(); // 本结点 p
            q.pop();

            for (int ch = 0; ch < 26; ch++) {
                if (tr[p][ch]) { // 如果本结点的下一个字符可以是 ch，才继续看
                    int son = tr[p][ch];
                    int j = fail[p]; 
                    // 拿到 p 的 fail，然后看 fail[p] 这个点的下一个字符可否是 ch
                    // 即判断 tr[fail[p]][ch] 是否存在
                    // 如果存在，则 son 的 fail 就是 tr[fail[p]][ch]
                    while (j && !tr[j][ch]) {
                        j = fail[j];
                    }
                    if (tr[j][ch]) {
                        j = tr[j][ch];
                    }
                    fail[son] = j;
                    q.push(son);
                }
            }
        }
    }
};

可以看到，甚至在 trie 树上更容易理解 fail 数组，回头再看 kmp 的 ne 数组，突然很不理解为啥之前老是记不住咋求。