1. 为什么需要 BM 算法？

在文本编辑器中搜索一个词，或者使用 grep 命令时，速度之所以快，很大程度上归功于 BM 算法及其变种。

传统的（朴素）字符串匹配是从左到右，一个字符一个字符地比。如果文本有一百万字，效率非常低。 BM 算法的核心优势在于“跳跃”：当发现不匹配时，它不是移动一位，而是利用规则一次性向后滑动多位。

核心结论：模式串（要找的词）越长，BM 算法通常越快。这是反直觉的，但在 BM 算法中是事实。

2. BM 算法的两个“反常识”设计

在深入规则之前，必须记住 BM 算法的两个独特行为：

从后往前比：虽然模式串是相对于文本向右移动的，但在比较每一个字符时，BM 是从模式串的末尾开始倒着比的。
贪心跳跃：算法同时参考两条规则（坏字符、好后缀），哪条规则能让模式串向右跳得更远，就听谁的。

3. 核心规则一：坏字符规则 (Bad Character Rule)

这是最直观的规则。

场景

当我们从后往前比较时，发现文本中的某个字符（叫它 X）和模式串对应位置的字符不匹配。这个 X 就是坏字符。

策略

既然 X 导致了不匹配，我们就在模式串里找找：“我的模式串里有没有 X 这个字？”

情况 A：模式串里根本没有 X
- 结论：既然模式串里没这个字，那么只要模式串还覆盖着文本中的 X，就绝不可能匹配。
- 操作：直接把整个模式串搬到 X 的后面。
- 效果：直接跳过一大段，效率极高。
情况 B：模式串里有 X
- 结论：虽然现在对不上，但也许滑一滑，把模式串里的 X 和文本里的 X 对齐，就能匹配了。
- 操作：移动模式串，让模式串中最靠右的 X 与文本中的 X 对齐。

图解示例

假设文本是 ...C D E F...，模式串是 A B C D。

文本:  ... C  D  E  F ...
模式:      A  B  C  D
                    ^ (比较 D 和 F，不匹配！F 是坏字符)

分析：模式串 ABCD 里没有 F。
操作：直接跳过 F。

Plaintext

文本:  ... C  D  E  F ...
模式:                 A  B  C  D

(一下子跳过了整个模式串的长度)

4. 核心规则二：好后缀规则 (Good Suffix Rule)

这是一条“以此类推”的规则，用于处理部分匹配的情况。

场景

我们在从后往前比较时，末尾的几个字符已经匹配成功了（这部分叫好后缀），但在中间某个位置卡住了。

策略

既然尾巴（好后缀）已经匹配了，我们能不能利用这个已知信息？

情况 A：模式串前面还有“好后缀”
- 逻辑：模式串里有没有另一段和“好后缀”长得一样的子串？
- 操作：把模式串移动一下，让前面那个重复的子串，对准现在文本里匹配好的位置。
情况 B：模式串前面没有完整的“好后缀”
- 逻辑：虽然没有完全一样的重复段，但也许好后缀的一部分（后缀的后缀）出现在了模式串的开头（前缀）？
- 操作：移动模式串，让头部和尾部重合的部分对齐。
情况 C：啥都没有
- 操作：直接把整个模式串滑过去。

图解示例

1. 对应情况 A（模式串里有重复的好后缀）

假设模式串为 B A B ... B A B，文本与之匹配了一部分 B A B 后发现不匹配。

文本:  ... X  B  A  B ...
模式:      B  A  B ... B  A  B
           ^  ^  ^     ^  ^  ^
           (重复部分)   (好后缀)

分析：好后缀是 BAB。模式串的前半段也有一个 BAB。
操作：移动模式串，让前面的 BAB 对齐文本现在的 BAB。

2. 对应情况 B（好后缀的后缀匹配模式串的前缀）

假设模式串为 A B ... C A B，好后缀是 CAB。

文本:  ... X  C  A  B ...
模式:      A  B ... C  A  B
           ^  ^     ^  ^  ^
           (前缀)    (好后缀 CAB)

分析：好后缀 CAB 在模式串里没有完整重复。但好后缀的后缀 AB 与模式串的前缀 AB 吻合。
操作：移动模式串，让开头的前缀 AB 对齐文本末尾的 AB。

3. 对应情况 C（完全没关系）

假设模式串为 D E F，好后缀 F。

文本:  ... X  F ...
模式:      D  E  F
              ^
             (好后缀)

分析：好后缀 F，模式串前面既没有 F，前缀也跟 F 没关系。
操作：直接把整个模式串跳过 F。

5. 完整工作流程演练

让我们用一个经典的例子，模拟计算机的视角。

文本 (Text): HERE IS A SIMPLE EXAMPLE
模式 (Pattern): EXAMPLE

第一轮比较

位置: 0123456...
文本: HERE IS A SIMPLE EXAMPLE
模式: EXAMPLE
      ^^^^^^^

比较方向：从模式串末尾（‘E’）对应文本的 ‘S’（索引 6）。
发现：S 和 E 不匹配。
坏字符：S。
决策：
- 模式串 EXAMPLE 里没有 S。
- 操作：直接将模式串移到 S 后面（向右滑动 7 位）。模式串起始位置从 0 变到 7。

第二轮比较

位置: ...6789...
文本: ...S A SIMPLE EXAMPLE
模式:     EXAMPLE
          ^^^^^^

(注：模式串起始位置为 7，末尾字符 ‘E’ 对齐文本的第 13 位 ‘P’)

比较方向：从末尾开始。
发现：文本的 P (索引 13) 和模式串的 E 不匹配。
坏字符：P。
决策：
- 模式串里有 P（倒数第 3 位，索引 4）。
- 操作：将模式串向右滑动，让模式串里的 P 对齐文本的 P。
- 移动量：末尾索引 6 - P的索引 4 = 2 位。
- 新起始位置：7 + 2 = 9。

第三轮比较

位置: ...9...
文本: ... SIMPLE EXAMPLE
模式:    EXAMPLE
         ^^^^^^^

(注：模式串起始位置为 9，覆盖文本 SIMPLE)

比较方向：从后往前。
- E (模) = E (文)
- L (模) = L (文)
- P (模) = P (文)
- M (模) = M (文)
- A (模) ≠ I (文) (索引 11)
发现：坏字符 I，好后缀 MPLE。
决策：
- 坏字符规则：I 不在模式串中。单纯用此规则可移动让模式串越过 I。
- 好后缀规则：好后缀是 MPLE。
  - 模式串其他地方有 MPLE 吗？无。
  - 模式串有前缀匹配 MPLE 的后缀吗？有！前缀 E 匹配后缀 E。
- 操作：移动模式串，让开头的前缀 E 对齐文本中刚刚匹配位置的 E (索引 15)。
- 移动量：6 位 (从位置 9 跳到 15)。

第四轮比较

位置: ...15...
文本: ...LE EXAMPLE
模式:     EXAMPLE
          ^^^^^^^

(注：模式串起始位置 15，末尾对齐文本第 21 位 ‘P’)

比较方向：从末尾开始。
发现：模式串 E ≠ 文本 P。
坏字符：P。
决策：
- 模式串里有 P。
- 操作：对齐 P。向右滑动 2 位。
- 新起始位置：15 + 2 = 17。

第五轮比较

位置: ...17...
文本: ...LE EXAMPLE
模式:       EXAMPLE
            ^^^^^^^

比较方向：从后往前。
结果：全部匹配！搜索成功。

6. 性能总结

BM 算法之所以是工业界的宠儿，归结于以下几点：

最佳时间复杂度： $O(N/M)$ $O (N / M)$ 。
- $N$ 是文本长度， $M$ 是模式串长度。
- 意味着：模式串越长，跳得越远，速度越快。这是 KMP 算法做不到的。
平均性能：在处理自然语言（英文、代码）时，BM 算法通常比 KMP 快 3-5 倍。
最差情况： $O(N \times M)$ 。虽然理论存在，但在实际文本搜索中极少遇到。

7. C++ 代码实现

以下是一个包含坏字符规则和好后缀规则完整实现的 BM 算法示例。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// --- 预处理坏字符规则 ---
void getBadChar(const string& p, vector<int>& badChar) {
    int m = p.size();
    // 初始化为 -1
    for (int i = 0; i < 256; i++) {
        badChar[i] = -1;
    }
    // 记录模式串中每个字符最后出现的位置
    for (int i = 0; i < m; i++) {
        badChar[(unsigned char)p[i]] = i;
    }
}

// --- 预处理好后缀规则 ---
// suffix[i] 表示 pattern[0...i] 和 pattern 的最长公共后缀长度
void getSuffix(const string& p, vector<int>& suffix) {
    int m = p.size();
    suffix[m - 1] = m;
    for (int i = m - 2; i >= 0; i--) {
        int j = i;
        while (j >= 0 && p[j] == p[m - 1 - (i - j)]) {
            j--;
        }
        suffix[i] = i - j;
    }
}

void getGoodSuffix(const string& p, vector<int>& gs) {
    int m = p.size();
    vector<int> suffix(m);
    getSuffix(p, suffix);

    // 初始化：如果没有匹配的好后缀，直接移动 m 位
    // 同时也涵盖了 Case 3 (什么都没匹配到) 和 Case 2 的默认情况
    for (int i = 0; i < m; i++) {
        gs[i] = m;
    }

    // Case 2: 模式串头部有子串匹配好后缀的后缀
    int j = 0;
    for (int i = m - 1; i >= 0; i--) {
        if (suffix[i] == i + 1) { // 找到了一个前缀等于后缀
            // 将剩余的部分 fill 进 gs
            for (; j < m - 1 - i; j++) {
                if (gs[j] == m) {
                    gs[j] = m - 1 - i;
                }
            }
        }
    }

    // Case 1: 模式串中有子串与好后缀完全匹配
    for (int i = 0; i <= m - 2; i++) {
        gs[m - 1 - suffix[i]] = m - 1 - i;
    }
}

// --- BM 搜索主函数 ---
int boyerMoore(const string& text, const string& pattern) {
    int n = text.size();
    int m = pattern.size();
    if (m == 0) return 0;

    vector<int> badChar(256);
    vector<int> goodSuffix(m);

    getBadChar(pattern, badChar);
    getGoodSuffix(pattern, goodSuffix);

    int s = 0; // s 是对齐位置（shift）
    while (s <= n - m) {
        int j = m - 1;

        // 从后往前比对
        while (j >= 0 && pattern[j] == text[s + j]) {
            j--;
        }

        if (j < 0) {
            // 匹配成功，返回下标
            return s;
            // 如果需要找下一个匹配: s += goodSuffix[0];
        } else {
            // 坏字符规则跳跃距离
            int bcShift = j - badChar[(unsigned char)text[s + j]];
            
            // 好后缀规则跳跃距离
            int gsShift = goodSuffix[j];

            // 取较大者作为跳跃步数
            s += max(bcShift, gsShift);
        }
    }
    return -1;
}

int main() {
    string text = "HERE IS A SIMPLE EXAMPLE";
    string pattern = "EXAMPLE";
    
    int result = boyerMoore(text, pattern);
    
    if (result != -1)
        cout << "Pattern found at index " << result << endl;
    else
        cout << "Pattern not found" << endl;
        
    return 0;
}

Boyer-Moore (BM) 字符串匹配算法

1. 为什么需要 BM 算法？

2. BM 算法的两个“反常识”设计

3. 核心规则一：坏字符规则 (Bad Character Rule)

场景

策略

图解示例

4. 核心规则二：好后缀规则 (Good Suffix Rule)

场景

策略

图解示例

1. 对应情况 A（模式串里有重复的好后缀）

2. 对应情况 B（好后缀的后缀匹配模式串的前缀）

3. 对应情况 C（完全没关系）

5. 完整工作流程演练

第一轮比较

第二轮比较

第三轮比较

第四轮比较

第五轮比较

6. 性能总结

7. C++ 代码实现