52 · KMP 与字符串匹配

在长串 s1 里找模式串 s2 的所有出现位置，暴力做法是：把 s2 对到每个起点上，逐字符比。最坏 O(|s1|·|s2|)——s1 = s2 = 10⁶ 个 a 时是 10¹² 次比较，必然超时。KMP 把“失配之后从哪一位重新开始比”预先算进一个数组，于是 s1 的指针永不回退，总时间 O(|s1| + |s2|)。

先把这一节的 4 样新东西拆开。核心只有 5 行，但要把 5 行写对，得先知道每一行在维护什么。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;
char s[MAXN];                  // s[1] 是第一个字符，s[0] 闲置

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> (s + 1);            // 读到 s[1] 起始的位置
    int n = strlen(s + 1);     // 串长
    cout << n << " " << s[1] << " " << s[n] << "\n";
    return 0;
}
// 输入 abcde → 输出 5 a e

const int MAXN = 1000005;
int f[MAXN];

// s 从 s[1] 开始，长度 m
void buildFail(const char* s, int m) {
    f[1] = 0;                                  // 单个字符没有 border
    for (int i = 2, j = 0; i <= m; ++i) {      // j 在这里声明：跨轮保留
        while (j && s[i] != s[j + 1]) j = f[j]; // 失配：跳到次长 border
        if (s[i] == s[j + 1]) ++j;              // 匹配：border 延长 1
        f[i] = j;
    }
}

// s = "aabaaab" → f[1..7] = 0 1 0 1 2 2 3

for (int i = 1, j = 0; i <= n; ++i) {
    while (j && s1[i] != s2[j + 1]) j = f[j];   // 失配：沿 fail 后退
    if (s1[i] == s2[j + 1]) ++j;                // 这一位对上了
    if (j == m) {                               // 整串对上
        cout << i - m + 1 << "\n";              // 起点（1 基）
        j = f[j];                               // 允许重叠，继续找
    }
}

const int MAXN = 2000005;
int z[MAXN];

void getZ(const char* t, int n) {          // t 从 t[1] 开始
    z[1] = n;
    int l = 1, r = 0;
    for (int i = 2; i <= n; ++i) {
        z[i] = 0;                                      // 清掉上一次运行的值
        if (i <= r) z[i] = min(z[i - l + 1], r - i + 1); // 盒子内先抄
        while (i + z[i] <= n && t[1 + z[i]] == t[i + z[i]]) ++z[i];
        if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; }
    }
}

// t = "aaa" → z = 3 2 1

① 预处理：对 s2 做 KMP，得到 f[1..m]
     f[1] = 0; j = 0
     for i = 2..m:
         while j > 0 且 s2[i] != s2[j+1]: j = f[j]
         if s2[i] == s2[j+1]: j++
         f[i] = j

② 匹配：扫一遍 s1
     j = 0
     for i = 1..n:
         while j > 0 且 s1[i] != s2[j+1]: j = f[j]
         if s1[i] == s2[j+1]: j++
         if j == m: 输出 i-m+1;  j = f[j]

③ 输出 f[1..m]

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;
char s1[MAXN], s2[MAXN];
int f[MAXN];                       // f[i]：s2 前 i 个字符的最长 border 长度

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> (s1 + 1) >> (s2 + 1);   // 1 基下标
    int n = strlen(s1 + 1), m = strlen(s2 + 1);

    // ① 预处理：s2 匹配自己，求出 f[1..m]
    f[1] = 0;                                  // 单字符没有非本身的 border
    for (int i = 2, j = 0; i <= m; ++i) {
        while (j && s2[i] != s2[j + 1]) j = f[j];   // 失配：沿 border 链后退
        if (s2[i] == s2[j + 1]) ++j;                // 对上了：border 延长 1
        f[i] = j;
    }

    // ② 匹配：i 扫 s1，j 记录已匹配长度
    for (int i = 1, j = 0; i <= n; ++i) {
        while (j && s1[i] != s2[j + 1]) j = f[j];
        if (s1[i] == s2[j + 1]) ++j;
        if (j == m) {                          // 出现一次
            cout << i - m + 1 << "\n";
            j = f[j];                          // 允许重叠，退到最长 border 继续
        }
    }

    // ③ 输出 f[1..m]，空格分隔，最后一个后换行
    for (int i = 1; i <= m; ++i) {
        cout << f[i];
        cout << (i == m ? "\n" : " ");
    }
    return 0;
}

fail 数组的第二大用途是求周期。一个串 s（长 n）的周期 p 指：对所有 i + p ≤ n 都有 s[i] = s[i+p]。等价说法是“s 有长度 n − p 的 border”。于是最小周期 = n − f[n]。

    // 假设 s[1..n] 与 f[1..n] 已经算好
    int p = n - f[n];                       // 最小周期
    // 完整循环节：n 能整除 p 时，s 由 n/p 个相同的块拼成
    int blocks = (n % p == 0) ? n / p : 0;  // 0 表示“不完整周期”
    cout << p << " " << blocks << "\n";

    // 全部 border 长度（从长到短）：沿 f 链走
    for (int k = f[n]; k > 0; k = f[k])
        cout << k << " ";

Z 函数是 KMP 的“兄弟”：它直接给出“每个后缀与整个串前缀的最长公共前缀”。把模式串拼在主串前面、中间加一个不在字符集里的分隔符，一次 Z 就能得到所有匹配位置。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2000005;              // |s1| + |s2| + 1 再留余量
char t[MAXN];
int z[MAXN];

void getZ(int n) {                     // t 从 t[1] 开始
    z[1] = n;
    int l = 1, r = 0;
    for (int i = 2; i <= n; ++i) {
        z[i] = 0;
        if (i <= r) z[i] = min(z[i - l + 1], r - i + 1);   // 盒子内先抄
        while (i + z[i] <= n && t[1 + z[i]] == t[i + z[i]]) ++z[i];
        if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string a, b;
    cin >> a >> b;                     // a 主串，b 模式串
    int n = a.size(), m = b.size();

    for (int i = 1; i <= m; ++i) t[i] = b[i - 1];
    t[m + 1] = '#';                    // 分隔符：不在字符集里，跨界的匹配立刻失败
    for (int i = 1; i <= n; ++i) t[m + 1 + i] = a[i - 1];

    int N = m + 1 + n;
    getZ(N);
    for (int i = m + 2; i <= N; ++i)
        if (z[i] >= m) cout << i - m - 1 << "\n";   // 起点 = i - (m + 1)
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;
char s[MAXN];
int f[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int L;
    cin >> L;
    cin >> (s + 1);                    // 1 基

    f[1] = 0;
    for (int i = 2, j = 0; i <= L; ++i) {
        while (j && s[i] != s[j + 1]) j = f[j];   // 沿 border 链后退
        if (s[i] == s[j + 1]) ++j;
        f[i] = j;
    }

    // 最小周期 = 长度 - 最长 border
    cout << L - f[L] << "\n";
    return 0;
}