字符串匹配的Boyer-Moore算法

Boyer-Moore算法是一种高效的字符串匹配算法，由Robert S. Boyer和J Strother Moore在1977年提出。它通过从右向左比较模式串与文本，并利用两种启发式规则（坏字符规则和好后缀规则）来跳过不必要的比较，从而在平均情况下达到亚线性时间复杂度。

算法核心思想

1. 从右向左比较模式串和文本中的对应字符
2. 当发现不匹配时，根据预计算的信息尽可能大地滑动模式串
3. 使用坏字符规则和好后缀规则来确定滑动距离

详细步骤

步骤1：预处理阶段 - 构建坏字符表
坏字符规则处理模式串中某个字符与文本不匹配时的情况。

构建坏字符表（bad character table）：

• 对于模式串中的每个字符，记录它最后一次出现的位置（从右数起）
• 如果字符不在模式串中，滑动距离为模式串长度

示例：模式串"EXAMPLE"

字符: E X A M P L E
位置: 6 5 4 3 2 1 0（从右向左索引）
坏字符表:
E → 0（最右边E的位置）
X → 5
A → 4
M → 3
P → 2
L → 1
其他字符 → -1（表示不在模式串中）

步骤2：预处理阶段 - 构建好后缀表
好后缀规则处理当模式串的后缀与文本匹配，但某个前缀不匹配时的情况。

构建好后缀表（good suffix table）：

1. 首先构建后缀数组suffix：
   • suffix[i] = 以i结尾的子串与模式串后缀匹配的最大长度
2. 然后构建好后缀移位数组shift：
   • 情况1：模式串中有另一个子串与当前好后缀匹配
   • 情况2：模式串的前缀是好后缀的后缀

示例：模式串"EXAMPLE"

好后缀表需要更复杂的计算，这里简化说明原理

步骤3：匹配过程
从文本开头开始，将模式串与文本对齐，从右向左比较字符。

具体匹配流程：

1. 初始化：i = 0（模式串在文本中的起始位置）
2. 当i ≤ n - m时（n为文本长度，m为模式串长度）：
   • 从j = m-1开始，从右向左比较模式串和文本
   • 如果所有字符都匹配，找到匹配位置i
   • 如果发现不匹配：
     • 计算基于坏字符规则的滑动距离
     • 计算基于好后缀规则的滑动距离
     • 选择较大的距离作为实际滑动距离
   • i增加滑动距离

步骤4：坏字符规则应用
当在位置j发现不匹配时：

• 坏字符c = 文本中与模式串位置j对应的字符
• 在坏字符表中查找c在模式串中最右出现位置（在j左边）
• 滑动距离 = j - bc_table[c]（如果bc_table[c] < j）
• 如果字符不在模式串中，滑动整个模式串长度

步骤5：好后缀规则应用
当已有长度为k的后缀匹配时：

• 在好后缀表中查找匹配的后缀在模式串中其他位置的出现
• 滑动距离 = m - 1 - 最右边的匹配位置
• 如果没有完全匹配，找最长的前缀与好后缀的后缀匹配

完整示例演示
文本："HERE IS A SIMPLE EXAMPLE"
模式串："EXAMPLE"

匹配过程：

1. 初始对齐：
   文本：HERE IS A SIMPLE EXAMPLE
   模式：EXAMPLE
   从右比较：E≠S，应用坏字符规则，滑动3位

2. 第二次对齐：
   文本：HERE IS A SIMPLE EXAMPLE
   模式： EXAMPLE
   从右比较：E≠P，应用坏字符规则，滑动2位

3. 继续这个过程直到找到完全匹配

算法复杂度分析

• 最坏情况：O(mn)（当文本和模式串都是重复字符时）
• 平均情况：O(n/m)（亚线性时间，非常高效）
• 预处理时间：O(m + σ)（σ为字符集大小）

优化技巧

1. 可以只使用坏字符规则，简化实现但仍保持较好性能
2. 对于短模式串，坏字符规则通常足够有效
3. 好后缀规则在模式串有重复子串时效果更好

Boyer-Moore算法在实际应用中非常高效，特别是在文本较长、字符集较大的情况下，其跳过大量不必要的比较使得性能优于朴素的字符串匹配算法。