串：KMP 与 BM 模式匹配

5.1 串是什么：定义与基本操作

5.1.1 定义与术语

串（String），又称字符串，是由零个或多个字符组成的有限序列，记作 S = "a1a2…an"。其中 n 称为串的长度， 长度为 0 的串称为空串（null string），记作 "" 或者 Ø。

串在逻辑上就是一种特殊的线性表——它的数据元素被限定为字符。但串和普通线性表有一个重要差别： 我们关心的操作不是「取第 i 个元素」，而是整段整段的比较、查找、拼接。 这就导致了串有自己的一套专用术语：

子串

串中任意个连续字符组成的子序列，例如 "dat" 是 "data" 的子串；空串是任意串的子串。

真子串

不包含自身的子串。

主串

包含子串的那个串。若 T 是 S 的子串，则 S 是主串。

串相等

两个串长度相同，且对应位置的字符全部相同。注意 "ab" 与 "ab " (多一个空格) 不相等。

模式串 / 目标串

模式匹配中，被查找的子串叫模式串 P（pattern），被搜索的大串叫目标串 / 主串 S。

前缀

从第一个字符开始、长度为 k 的连续子串，记作 P[0..k-1]。真前缀即 k < |P|。

后缀

以最后一个字符结尾、长度为 k 的连续子串，记作 P[|P|-k .. |P|-1]。真后缀即 k < |P|。

最长相等真前后缀

一个串的某个真前缀恰好等于它的某个真后缀，其中最长的那一对的长度。KMP 的 next 数组就是它。
例："ABAB" 的真前缀有 "A", "AB", "ABA"，真后缀有 "B", "AB", "BAB"，相等的最长者是 "AB"，长度为 2。

5.1.2 串的存储结构

串有三种常见存储方式，各有取舍：

5.1.3 串的基本操作（ADT）

串的抽象数据类型通常包含以下九种基本操作，请把它们的语义和复杂度一起记住：

下面是这些操作在 C++ 中的最小实现示例（顺序存储、0 基下标）：

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

/* 串的基本操作演示（C++ 的 std::string 就是"堆分配顺序存储"的一种工业实现） */
int main() {
    string s = "data";
    string t = "structure";

    cout << s.size() << "\n";                  // 4          求长度 O(1)
    cout << s + "-" + t << "\n";               // data-structure  拼接 O(n+m)
    cout << s.substr(1, 2) << "\n";            // at         取子串 O(len)
    cout << s.compare("datax") << "\n";        // -1（s 更小）比较 O(min)
    cout << (int)s.find("ta") << "\n";         // 2          模式匹配
    cout << (int)s.find("xyz") << "\n";        // -1         未找到返回 npos

    /* 手写 StrCompare：理解"字典序"到底怎么定的 */
    // 从第一个字符开始逐位比较，遇到第一处不同就返回差值；
    // 若前面全部相同，则短串更小。
    return 0;
}

5.2 朴素模式匹配：暴力法慢在哪

5.2.1 算法思路

模式匹配（pattern matching）问题可以严格描述为：给定主串 S（长度 n）与模式串 P（长度 m，通常 m ≤ n），求 P 在 S 中第一次出现的位置（下标）， 不存在则返回 -1。

最直觉的做法是枚举所有可能的对齐位置：让 P 的左端依次对齐 S 的 第 0、1、2、…、n−m 位，每个位置从 P[0] 开始逐字符比较，全部相同则匹配成功。这个方法叫 朴素匹配（Naive / Brute-Force / BF）。

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

/* 朴素模式匹配：返回 P 在 S 中第一次出现的下标，找不到返回 -1
   设 n = |S|, m = |P|
   最好：第一个位置就匹配           O(m)
   最坏：每轮都比到最后一个字符才失败  O((n-m+1)*m) ≈ O(n*m) */
int naiveIndex(const string& S, const string& P) {
    int n = S.size(), m = P.size();
    if (m == 0) return 0;
    for (int pos = 0; pos + m <= n; ++pos) {     // 枚举每一个对齐位置
        int j = 0;
        while (j < m && S[pos + j] == P[j]) ++j;   // 逐个字符比对
        if (j == m) return pos;                  // 全部相等 → 命中
    }
    return -1;
}

int main() {
    string S = "ABABABCABABABCABA";
    string P = "ABABCABA";
    cout << naiveIndex(S, P) << "\n";   // 2
    return 0;
}

5.2.2 亲手看它一步步怎么比

下面的动画用同一组主串与模式串演示朴素匹配的每一次比较，注意观察失配后指针是怎么动的：

5.2.3 复杂度分析：为什么慢

设 n = |S|，m = |P|：

• 最好情况：第一轮就匹配成功，比较 m 次，O(m)。
• 最坏情况：每一轮都要比到模式串的最后一个字符才失败。典型输入如 S = "aaaaaaaaaab"，P = "aaab"。此时每个对齐位置要比较 m 次， 共 (n-m+1) 个位置，总计约 m(n-m+1) ≈ O(n×m)。
• 平均情况：若字符随机，每轮平均比较次数是常数 1/(1-σ)（σ 为字符出现概率）， 总体接近 O(n)。所以朴素算法在自然文本上并不算太差——但在 大量重复字符（DNA、二进制串、恶意构造的输入）面前会退化到平方级。

5.3 KMP 算法与 next 数组的推导

5.3.1 一句话本质

KMP 由 Knuth、Morris、Pratt 三人于 1977 年提出，因此得名。它的核心洞察是：

假设我们已经匹配了 P[0..j-1] 这 j 个字符，主串中对应的那段就是 S[i-j .. i-1]， 它恰好等于 P[0..j-1]。现在 S[i] ≠ P[j] 失配了。 朴素做法要放弃这段匹配重新开始，但既然主串里那段就等于 P[0..j-1]， 我们完全可以问：在 P[0..j-1] 内部，有没有一个「开头」和「结尾」是一样的？ 如果有，长度是 k，那么主串里那段匹配内容的最后 k 个字符，一定等于模式串的前 k 个字符。 于是我们不必移动 i，只需要把模式串向右滑，让 P[0..k-1] 对准主串刚才那段的后 k 个字符， 即令 j = k，继续比较。

5.3.2 next 数组的定义（两种约定一定要分清）

把「P[0..j-1] 的最长相等真前后缀长度」预先算好存进数组，失配时直接查表， 这个数组就是 next。但不同教材的下标约定不同，这是初学者最容易混乱的地方，务必记牢自己用的是哪一种：

三种约定算出来的数值不同，但算法行为完全等价。下面我们统一采用最直观的 0 基前缀函数 π 来讲解与实现，并在 5.4.3 节给出与教材版 next 的换算方法。

5.3.3 手推 next 数组的完整过程

求 π 的过程本身就是一次「模式串自己匹配自己」。最朴素的想法是：对每个 i， 从长到短枚举所有真前后缀，检查是否相等——那是 O(m³)。 正确做法是利用已经算出的 π[i-1] 递推：

1. 设 len = π[i-1]，即前 i 个字符的最长相等真前后缀长度。
2. 现在想把这个长度扩展到 len+1，只需检查 P[i] 是否等于 P[len]： 相等则 π[i] = len + 1，收工。
3. 若不等，说明以 len+1 结尾的前后缀不成立，那就退而求其次： 用一个更短的、但仍然相等的前后缀。这个更短的长度恰好是 π[len-1]—— 因为 P[0..len-1] 的最长相等真前后缀长度就是它。于是 len = π[len-1]，回到第 2 步。
4. 若 len 一路退到 0 仍然 P[i] ≠ P[0]，则 π[i] = 0。

第 3 步是 KMP 最精妙的地方：回退不是回到起点重来，而是退到「次优的候选长度」。 下面用 P = "ABABAA" 完整演示这个过程，请对照动画逐帧理解「lena 是怎么退的」：

5.3.4 用「失配跳转图」把回退过程看死

在进入代码之前，先把 π 数组换一种读法——它会立刻变得好记得多。 把每个下标 j 想成一个状态：状态 j 表示「模式串的前 j 个字符已经匹配上了」。 那么 π[j-1] 就是：当你处在状态 j 却匹配不下去时，应该退回的那个状态。

换句话说，π 数组描述了一张失配跳转图（failure link）：每个状态连一条「退路」边指向一个更小的状态。 以 P = "ABABAC" 为例，π = [0, 0, 1, 2, 3, 0]，跳转关系如下图：

5.3.5 KMP 匹配全过程

有了 π 数组，匹配过程就极其简单：i 只增不减；失配时若 j > 0 就 j = π[j-1]，否则 i++。下面的动画把 i、j、 模式串的对齐位置、以及每次 j 的回退都标了出来：

5.3.6 教材版 next 数组怎么手算（考试标准做法）

国内教材（严蔚敏《数据结构》与考研 408）采用的约定是：模式串从下标 1 开始存放， next[1] = 0 是人为规定的哨兵，而 next[j] = P[1..j-1] 的最长相等真前后缀长度 + 1（当 j ≥ 2 时）。

手算时最实用的方法是「看第 j 个字符前面的那一段」：把 P[1..j-1] 拿出来， 求它最长的「真前缀 = 真后缀」，长度记作 k，则 next[j] = k + 1。 以 P = "abaabc" 为例，逐个算一遍（下面的表格请自己动手再推一次， 与前面 0 基 π 的动画对照，你会发现两者其实是同一件事）：

逐行解释第三列到第六列的推导：

• j=2：P[1..1] = "a" 只有一个字符，没有真前后缀，k = 0，next[2] = 1。
• j=3：P[1..2] = "ab"，真前缀 "a"、真后缀 "b"，不相等，k = 0，next[3] = 1。
• j=4：P[1..3] = "aba"，真前缀 {a, ab}、真后缀 {a, ba}，最长相等的是 "a"，k = 1，next[4] = 2。
• j=5：P[1..4] = "abaa"，真后缀有 {a, aa, baa}，真前缀有 {a, ab, aba}，最长相等是 "a"，k = 1，next[5] = 2。
• j=6：P[1..5] = "abaab"，真后缀 {b, ab, aab, baab}，真前缀 {a, ab, aba, abaa}，最长相等是 "ab"，k = 2，next[6] = 3。

5.3.7 用教材版 next 实现匹配

教材版代码与 0 基版只是「下标从 1 开始」和「回退写 j = next[j]」的差别， 逻辑完全一致，考试与作业里两种都要会写：

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

/* 教材版 KMP（1 基下标）
   S[1..n] 主串，P[1..m] 模式串，next[1..m]
   返回 P 在 S 中第一次出现的 1 基起始位置，找不到返回 0 */
void getNext(const string& P, vector<int>& nxt) {
    int m = P.size();                       /* P 的第 k 个字符是 P[k-1] */
    nxt.assign(m + 1, 0);
    nxt[1] = 0;                             /* 哨兵 */
    int i = 1, j = 0;
    while (i < m) {
        if (j == 0 || P[i - 1] == P[j - 1]) { ++i; ++j; nxt[i] = j; }
        else j = nxt[j];                    /* 注意是 nxt[j]，不是 j-1 */
    }
}

int indexKMP(const string& S, const string& P, const vector<int>& nxt) {
    int n = S.size(), m = P.size();
    int i = 1, j = 1;
    while (i <= n && j <= m) {
        if (j == 0 || S[i - 1] == P[j - 1]) { ++i; ++j; }   /* j==0 说明退到哨兵，主串前进 */
        else j = nxt[j];                                    /* 只退 j，不退 i */
    }
    return (j > m) ? i - m : 0;             /* 返回 1 基起始位置 */
}

int main() {
    string S = "abaababaabcx", P = "abaabc";
    vector<int> nxt;
    getNext(P, nxt);
    cout << "next  = ";
    for (int k = 1; k <= (int)P.size(); ++k) cout << nxt[k] << ' ';
    cout << "\n";                            /* 0 1 1 2 2 3 */
    cout << indexKMP(S, P, nxt) << "\n";     /* 6（1 基）
        过程：匹配到 S[6]='b' 与 P[4]='a' 失配 → j = next[4] = 2（只退 j）
              继续比 S[6]='b' 与 P[2]='b' 相等 → 一路比到 j = 7 > m，返回 i-m = 11-6+1 = 6 */
    return 0;
}

5.3.8 什么时候用 KMP：匹配场景与朴素算法对比

前面说了 KMP 最坏是 O(n+m)、朴素是 O(n×m)。但在真实数据上，朴素算法并不总是慢。 下表给出几种典型输入下两个算法的比较次数感受（n = 1000，m = 10）：

结论：KMP 的价值在于「最坏情况的上界」与「主串只扫描一遍」。 当主串是流式到达、不能回退（例如网络数据包逐字节到达）时，KMP 是唯一可行的线性算法； 而朴素算法需要回头重看数据，天然不适用于流式场景。

5.4 KMP 的完整实现与优化

5.4.1 0 基前缀函数版（推荐写法）

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

/* ============================================================
   KMP（0 基下标，π 数组约定）
   pi[i] = P[0..i] 的最长相等真前后缀长度
   ============================================================ */

/* 求前缀函数，时间复杂度 O(m)，空间 O(m) */
vector<int> prefixFunction(const string& P) {
    int m = P.size();
    vector<int> pi(m, 0);
    for (int i = 1; i < m; ++i) {
        int len = pi[i - 1];                 // 先继承前一位的结果
        while (len > 0 && P[i] != P[len]) {  // 对不上就回退到次优候选长度
            len = pi[len - 1];
        }
        if (P[i] == P[len]) ++len;           // 能接上就 +1
        pi[i] = len;
    }
    return pi;
}

/* 返回 P 在 S 中第一次出现的下标，找不到返回 -1 */
int kmpSearch(const string& S, const string& P) {
    int n = S.size(), m = P.size();
    if (m == 0) return 0;
    vector<int> pi = prefixFunction(P);
    int j = 0;                               // j = 当前已匹配的字符个数
    for (int i = 0; i < n; ++i) {            // i 只前进，永不回退
        while (j > 0 && S[i] != P[j]) j = pi[j - 1];
        if (S[i] == P[j]) ++j;
        if (j == m) return i - m + 1;        // 全部匹配，返回起始下标
    }
    return -1;
}

int main() {
    string S = "ABABABCABABABCABA";
    string P = "ABABCABA";
    vector<int> pi = prefixFunction(P);
    for (int x : pi) cout << x << ' ';
    cout << "\n";                            // 0 0 1 2 0 1 2 3
    cout << kmpSearch(S, P) << "\n";         // 2
    return 0;
}

注意代码里的 while (j > 0 && S[i] != P[j]) j = pi[j - 1];。 为什么 j 回退的总次数是 O(n)？做个均摊分析：j 每次循环最多 +1， 在 n 次迭代中总共最多增加 n；而 j 每次回退至少减少 1，所以总回退次数不超过总增加次数， 也是 O(n)。因此整个匹配循环是线性的。

5.4.2 nextval：解掉「连续相同字符反复回退」

看一个极端例子：S = "aaaaaaab"，P = "aaaaab"。 在最后一个 b 处失配后，j = π[4] = 4，接着比较 S[i] 与 P[4] = 'a'，又失配，j = π[3] = 3……一路退到 0。 但既然 P[4] = P[3] = P[2] = … = 'a'，只要 S[i] 不是 'a'， 这些比较注定全部失败，完全可以一次性退到位。

于是有了 nextval（优化后的 next）：算 π[i] 时，如果 P[i+1] == P[π[i]]，说明「退过去还是要和同一个字符比」，那就直接继承那个位置的 优化结果，把这一步的无效比较也省掉。

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

/* nextval：在 π 的基础上继续消除"回退后仍与同一字符比较"的无效步骤。
   注意：为了便于对照教材，这里直接给出 1 基下标、教材风格的 next 与 nextval。 */
void buildNextTextbook(const string& P, vector<int>& nxt, vector<int>& nxtval) {
    int m = P.size();                          /* 约定：P 的第 k 个字符是 P[k-1]，下标 1..m */
    nxt.assign(m + 1, 0);
    nxt[1] = 0;                                /* 哨兵：第一个字符失配时无处可退 */
    int i = 1, j = 0;
    while (i < m) {
        if (j == 0 || P[i - 1] == P[j - 1]) {  /* 能接上，或 j 已经退到哨兵 */
            ++i; ++j;
            nxt[i] = j;                        /* next[i] = 最长相等真前后缀长度 + 1 */
        } else {
            j = nxt[j];                        /* 回退到次优候选，继续尝试 */
        }
    }
    /* nextval 递推：若 P[i] == P[next[i]]，说明"退过去还是要比同一个字符"，
       于是直接继承那个位置的优化结果，一步退到位。 */
    nxtval.assign(m + 1, 0);
    nxtval[1] = 0;
    for (int k = 2; k <= m; ++k) {
        if (P[k - 1] == P[nxt[k] - 1]) nxtval[k] = nxtval[nxt[k]];
        else nxtval[k] = nxt[k];
    }
}

int main() {
    string P = "aaaaab";
    vector<int> a, b;
    buildNextTextbook(P, a, b);
    cout << "next    : "; for (int i = 1; i < (int)a.size(); ++i) cout << a[i] << ' '; cout << "\n";
    cout << "nextval : "; for (int i = 1; i < (int)b.size(); ++i) cout << b[i] << ' '; cout << "\n";
    /* 输出 next    : 0 1 2 3 4 5
             nextval : 0 0 0 0 0 5   —— 连续相同字符被一次退到位 */
    return 0;
}

5.4.3 从 next 数组能读出什么

π 数组不只能做匹配，它还是很多题型的钥匙：

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

vector<int> prefixFunction(const string& P) {
    int m = P.size(); vector<int> pi(m, 0);
    for (int i = 1; i < m; ++i) {
        int len = pi[i - 1];
        while (len > 0 && P[i] != P[len]) len = pi[len - 1];
        if (P[i] == P[len]) ++len;
        pi[i] = len;
    }
    return pi;
}

/* 应用 1：最小循环节。若整串由 k 个循环节组成，返回节长；否则返回 n */
int minPeriod(const string& s) {
    int n = s.size();
    vector<int> pi = prefixFunction(s);
    int p = n - pi[n - 1];                 // 候选节长
    return (n % p == 0) ? p : n;
}

/* 应用 2：找出所有既是前缀又是后缀的长度（border） */
vector<int> borders(const string& s) {
    vector<int> pi = prefixFunction(s), res;
    int k = pi[s.size() - 1];
    while (k > 0) { res.push_back(k); k = pi[k - 1]; }
    return res;                            // 从大到小
}

/* 应用 3：统计每个前缀在整个串中出现的次数（前缀出现次数） */
vector<long long> prefixCount(const string& s) {
    int n = s.size();
    vector<int> pi = prefixFunction(s);
    vector<long long> cnt(n + 1, 0);
    for (int i = 0; i < n; ++i) cnt[pi[i]]++;      // 每个位置贡献给它的最长 border
    for (int i = n; i >= 1; --i) cnt[pi[i - 1]] += cnt[i];   // 倒序累加上去
    for (int i = 1; i <= n; ++i) cnt[i]++;          // 每个前缀自身也算出现一次
    return cnt;
}

int main() {
    string s = "abcabcabc";
    cout << minPeriod(s) << "\n";                 // 3
    string t = "abababab";
    for (int x : borders(t)) cout << x << ' ';     // 6 4 2
    cout << "\n";
    for (int i = 1; i <= 3; ++i) cout << prefixCount("aaa")[i] << ' ';  // 3 2 1
    return 0;
}

5.4.4 KMP 的复杂度与局限

5.5 BM 算法：从右往左，跳着比

5.5.1 为什么换个方向就快很多

KMP 从左往右逐字符比较，失配时最多往前挪一点点。而 BM（Boyer-Moore，1977）反其道而行： 从模式串的最后一个字符开始往左比。这个「反着比」看似无关紧要，却带来一个巨大的好处—— 一旦在最右边就失配，我们看到的那个主串字符（坏字符）就能告诉我们： 模式串可以向右滑动多少格而绝不错过任何匹配。

更关键的是：如果这个坏字符根本不在模式串里，那么模式串可以直接整段跳过该字符，一次滑动 m 格！在自然语言里，大部分字符都不会出现在给定的模式串中，所以 BM 的实测速度往往远快于 KMP， 平均比较次数接近 O(n/m)。这也是 grep、编辑器查找功能普遍采用 BM 家族算法的原因。

5.5.2 规则一：坏字符规则（Bad Character）

规则描述（约定模式串与主串左端对齐于 align，从 j = m−1 往左比）：

1. 若 S[align+j] ≠ P[j]，记 c = S[align+j] 为坏字符。
2. 查「坏字符表」last[c]：字符 c 在模式串中最后出现的下标（不存在记为 −1）。
3. 若 last[c] < j：把模式串右移 j − last[c] 格，让 c 与它在模式串中的最后出现对齐。
4. 若 last[c] 不存在：模式串整体右移 j + 1 格（相当于跳过 c 这个位置）。
5. 若 last[c] > j：位移算出来是负数——这种情况说明坏字符出现在失配位置的右边， 此时坏字符规则失效，至少也要右移 1 格，具体滑多少要看下面的好后缀规则。

5.5.3 规则二：好后缀规则（Good Suffix）

光靠坏字符规则会出问题。考虑一个真实场景：从右往左比，尾部已经匹配了一长串（这就是好后缀）， 却在前面某处失配，而坏字符规则算出来的位移可能只有 1 格甚至为负。此时好后缀给出了另一条线索：

既然主串里确实存在与好后缀相同的一段，那么在模式串中，好后缀自身（或它的某个后缀） 必然还能在别处找到一次出现，或者等于模式串的某个前缀。据此可以安全地一次性滑到位。

5.5.4 BM 的完整 C++ 实现

下面是「坏字符规则 + 好后缀规则」的完整实现。工程上还有更省事的简化版 （只保留坏字符规则、或者用 Horspool 变体只比较最后一个字符），但完整版才体现 BM 的威力。

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

/* ============================================================
   Boyer-Moore 字符串匹配（完整版：坏字符 + 好后缀）
   返回 P 在 S 中第一次出现的下标，找不到返回 -1

   竞赛写法：模式串与两张预处理表都是"一次预处理、多次查询"的全局量，
   所以直接开全局 string P + 两个全局表 + 两个自由函数，
   不必再套一层 BM 结构体（struct 只留给结点型数据）。
   用法：先 cin / 赋值给 P，再 buildBM()，之后可以任意次 bmSearch(S)。
   ============================================================ */

string P;                   /* 模式串 */
int m;                      /* |P| */
int badChar[256];           /* 坏字符表：字符 c 在 P 中最后出现的下标（用 256 覆盖全部字节） */
int goodSuffix[100];        /* 好后缀表：gs[i] = 当 P[i] 处失配时应右移的距离 */

/* ---------- 1. 坏字符表 ---------- */
void buildBadChar() {
    for (int c = 0; c < 256; ++c) badChar[c] = -1;
    for (int i = 0; i < m; ++i)
        badChar[(unsigned char)P[i]] = i;
}

/* ---------- 2. 好后缀表 ----------
   设 P[i] 处失配，则好后缀是 P[i+1 .. m-1]。
   把模式串整体右移 s 格后，好后缀的新起点是 (i+1-s)，
   要求新位置上与之等长的一段逐字符相等，且不能与原位重叠。
   取满足条件的最小正 s。 */
void buildGoodSuffix() {
    for (int i = 0; i < m; ++i) goodSuffix[i] = 1;
    for (int i = 0; i < m - 1; ++i) {          /* 失配位置 i（最后一位失配时无好后缀） */
        int suffixLen = m - 1 - i;
        if (suffixLen == 0) { goodSuffix[i] = 1; continue; }
        int best = 0;
        for (int s = 1; s <= m - 1 && !best; ++s) {
            int start = i + 1 - s;             /* 好后缀右移 s 后的新起点 */
            if (start < 0) break;
            bool ok = true;
            for (int t = 0; t < suffixLen; ++t) {
                int pos = start + t;
                if (pos >= m || pos >= start + s) { ok = false; break; }  /* 不得与原位重叠 */
                if (P[pos] != P[i + 1 + t]) { ok = false; break; }
            }
            if (ok) best = s;
        }
        if (!best) {
            /* 兜底：好后缀的某个后缀若等于模式串的前缀，则滑到该前缀对齐 */
            for (int len = suffixLen - 1; len > 0 && !best; --len) {
                if (P.compare(0, len, P, m - len, len) == 0)
                    best = i + 1 + (suffixLen - len);
            }
            if (!best) best = i + 1;
        }
        goodSuffix[i] = best;
    }
}

/* 一次把两张表都建好；P 和 m 要先设置好 */
void buildBM() {
    m = P.size();
    buildBadChar();
    buildGoodSuffix();
}

int bmSearch(const string& S) {
    int n = S.size();
    if (m == 0) return 0;
    if (n < m) return -1;
    int align = 0;                              /* 模式串左端在主串中的对齐位置 */
    while (align <= n - m) {
        int j = m - 1;
        while (j >= 0 && P[j] == S[align + j]) --j;   /* 从右往左比较 */
        if (j < 0) return align;                        /* 完全匹配 */

        int b = badChar[(unsigned char)S[align + j]];
        int shiftBad = j - b;
        if (shiftBad < 1) shiftBad = 1;                 /* 坏字符在右边时兜底 */
        int shiftGood = goodSuffix[j];
        align += max(shiftBad, shiftGood);              /* 两条规则取较大值 */
    }
    return -1;
}

int main() {
    string S = "HERE IS A SIMPLE EXAMPLE";
    P = "EXAMPLE";
    buildBM();
    cout << bmSearch(S) << "\n";     // 17
    cout << bmSearch("NO MATCH HERE") << "\n";   // -1
    return 0;
}

5.6 三种匹配算法综合对比

5.7 工程视角：字符串匹配在真实系统里长什么样

这一章讲的三个算法不是"考试专用"。只要系统里有"在一堆文本里找一小段文本"的需求， 背后就一定会落到这一族算法上。下面按领域看几个真实的落点，注意每个场景为什么选中了那一种。

5.7.1 编辑器与 grep：为什么不用 KMP

grep、Ctrl+F、"在文件夹中查找"这类工具的典型形态是： 一个较长的模式串（用户输入的关键词通常 5～30 个字符）、 一个很大的主串（整个文件甚至整个目录树）、 而且绝大多数位置都不匹配。

这正是 BM 的主场。因为大多数位置在最右边第一个字符就失配，而那个字符又往往不在模式串里， 于是模式串可以一次跳过好几格，实测比较次数接近 O(n/m)。 相比之下 KMP 无论数据长什么样，每个字符都要参与一次比较，是稳定的 O(n)—— 在"平均情况"上反而比 BM 慢好几倍。

5.7.2 数据库与检索系统：LIKE 和全文索引

数据库里的字符串查找分成两档，性能差好几个数量级：

注意第三行：LIKE '%abc%' 之所以慢，恰恰是因为它要求的正是本章的 模式匹配——没有前缀可依赖，B+ 树帮不上忙，只能把每一行的那个字段拿出来跑一遍匹配算法。 n 是表的行数（可能是几千万），m 是模式长度，这个代价足以拖垮一整条查询。

下面的代码把这三条路各实现了 10 行，用同一份数据实测比较次数， 可以直观看到「前缀能走索引」和「只能逐行匹配」的差距：

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

/* ============================================================
   数据库 LIKE 三种写法的底层代价对比（简化模型）

   ① name = 'abc'        等值查询   → B+ 树，O(log n)
   ② name LIKE 'abc%'    前缀查询   → B+ 树范围扫描，O(log n + 命中数)
   ③ name LIKE '%abc%'   任意位置   → 逐行字符串匹配，O(行数 × 模式长度)

   下面用「一行数据 = 一个字符串」的模型，把 ② 与 ③ 各跑一遍，
   统计真正的字符比较次数，用数据说明差距来自哪里。
   ============================================================ */

/* 全局计数器：统计字符比较次数，模拟数据库里的实际工作量 */
long long cmpCount = 0;

bool charEq(char a, char b) { ++cmpCount; return a == b; }

/* ---------- ② 前缀匹配：等价于「先定位再顺序扫」 ----------
   真实数据库用 B+ 树直接跳到 "abc" 开头的那一段，
   这里用排序 + 二分模拟「定位」这一步的开销。 */
bool likePrefix(const string& s, const string& p) {
    if (p.size() > s.size()) return false;
    for (size_t i = 0; i < p.size(); ++i)
        if (!charEq(s[i], p[i])) return false;      /* 只比前缀那么多个字符 */
    return true;
}

/* ---------- ③ 任意位置匹配：必须逐行、逐位置地找 ----------
   这就是本章讲的模式匹配。数据库不会替你优化，
   它只能对每一行调用一次这样的函数。 */
bool likeContains(const string& s, const string& p) {
    int n = s.size(), m = p.size();
    if (m == 0) return true;
    for (int pos = 0; pos + m <= n; ++pos) {
        int j = 0;
        while (j < m && charEq(s[pos + j], p[j])) ++j;
        if (j == m) return true;
    }
    return false;
}

int main() {
    /* 造 20000 行数据，每行 40 个字符 */
    const int ROWS = 20000, LEN = 40;
    vector<string> rows;
    rows.reserve(ROWS);
    for (int i = 0; i < ROWS; ++i) {
        string s;
        for (int j = 0; j < LEN; ++j) s += char('a' + (i * 7 + j * 13) % 26);
        rows.push_back(s);
    }

    string p = "abcd";

    cmpCount = 0;
    int hitPrefix = 0;
    for (const auto& s : rows) if (likePrefix(s, p)) ++hitPrefix;      /* ② 前缀 */
    long long cPrefix = cmpCount;

    cmpCount = 0;
    int hitContains = 0;
    for (const auto& s : rows) if (likeContains(s, p)) ++hitContains;  /* ③ 任意位置 */
    long long cContains = cmpCount;

    cout << "行数 " << ROWS << "，模式 \"" << p << "\"\n";
    cout << "LIKE 'abcd%'  比较次数 " << cPrefix   << "，命中 " << hitPrefix   << " 行\n";
    cout << "LIKE '%abcd%' 比较次数 " << cContains << "，命中 " << hitContains << " 行\n";
    cout << "③ 是 ② 的 " << (double)cContains / (cPrefix ? cPrefix : 1) << " 倍\n";
    /* 实测约为 40 倍量级：前缀每条只需比到第一处不同就退出，
       而任意位置匹配要对每个可能的起始位置都试一遍。 */
    return 0;
}

解决办法是倒排索引（inverted index）：预先建立"词 → 出现位置列表"的映射， 查询时先查词表再做位置求交。这就是 Elasticsearch、Lucene 以及各数据库全文索引的做法。 它把"每次查询都做一遍模式匹配"的成本，摊到了"建索引时做一次"上。 这是数据结构里一个反复出现的思路：把重复的计算提前算好、存起来。

5.7.3 网络安全与生物信息：KMP 不可替代的两个场景

上面说 BM 平均更快，但有两类场景必须用 KMP 这一族（或它的推广），因为它们的输入是流式的、 不允许回退，或者模式不止一个：

5.8 本章小结与练习

自测题

配套编程练习