Boyer-Moore 字符串匹配算法：原理与实践

Boyer-Moore 算法是一种经典的字符串匹配算法，它通过构建坏字符规则和好后缀规则来加速匹配过程。与朴素的字符串匹配算法（如 Naive 算法）相比，Boyer-Moore 算法在处理大规模数据时具有更高的效率。

一、算法原理

1. 坏字符规则：当模式串中存在某个字符与文本中对应字符不相等时，我们可以利用这一信息跳过一部分文本，从而提高匹配速度。具体地，我们可以预先构建一个坏字符表，记录模式串中每个字符最后一次出现的位置。在匹配过程中，如果发现某个字符不相等，则将模式串向右滑动到坏字符表中该字符的最右位置的下一个位置。
2. 好后缀规则：当模式串中存在某个后缀子串与文本中对应前缀子串相等时，我们可以利用这一信息跳过一部分文本。具体地，我们可以预先构建一个好后缀表，记录模式串中每个后缀子串在模式串中的位置。在匹配过程中，如果发现某个后缀子串与文本中的前缀子串相等，则将模式串向右滑动到该后缀子串的最右位置的下一个位置。

二、实现细节

1. 预处理阶段：在预处理阶段，我们需要构建坏字符表和好后缀表。坏字符表的构建相对简单，只需要遍历一次模式串即可。而好后缀表的构建则需要使用到递归和动态规划的思想。
2. 匹配阶段：在匹配阶段，我们首先按照坏字符规则进行匹配，如果无法匹配成功，则再按照好后缀规则进行匹配。在每次滑动模式串之后，都需要更新坏字符表和好后缀表。

三、优化技巧

1. 使用跳跃表：为了加速滑动操作，我们可以使用跳跃表来存储模式串的位置信息。跳跃表的每个节点都记录了模式串中某个字符的位置，通过二分查找可以快速找到目标字符的位置。
2. 动态规划优化：对于某些特定的模式串，我们可以使用动态规划的思想来进一步优化算法性能。例如，当模式串中存在多个重复子串时，我们可以使用动态规划来避免重复计算滑动距离。

四、实例演示

下面是一个简单的 Python 代码实现 Boyer-Moore 算法：

```python
def build_bad_char_table(pattern):
n = len(pattern)
table = [-1] * 256 # 预处理坏字符表
for i in range(n):
table[ord(pattern[i])] = i
return table

def build_good_suffix_table(pattern):
n = len(pattern)
table = [-1] * n # 预处理好后缀表
j = n - 1 # 好后缀的起始位置
while j >= 0:
i = n - 1 # 好后缀的结束位置
while i > j:
if pattern[i] == pattern[j]:
table[j] = i + 1 # 好后缀长度为 i - j + 1
j = i - 1 # 继续向左寻找更长的后缀
else:
break # 好后缀结束位置向右移动一位
i = n - 1 # 重置 i 的值为 n - 1，继续寻找下一个好后缀的起始位置
return table

def boyer_moore_search(text, pattern):
n = len(pattern)
m = len(text)
table1 = build_bad_char_table(pattern) # 构建坏字符表
table2 = build_good_suffix_table(pattern) # 构建好后缀表
i = n - 1 # 从模式串末尾开始匹配
j = n - 1 # 从文本末尾开始匹配
while i < m:
if pattern[j] == text[i]: # 如果当前字符相等，继续匹配下一个字符
i += 1
j += 1
if j == n: # 如果模式串已经完全匹配上，返回匹配起始位置
return i - j + 1