BM 算法

### Boyer-Moore 算法的实现及原理 #### 1. 基本概念 Boyer-Moore (BM) 算法是一种高效的字符串匹配算法，其核心在于通过从模式串的 **末尾** 开始比较，并结合两种规则——**坏字符规则** 和 **好后缀规则** 来加速匹配过程[^2]。 #### 2. 时间复杂度分析 该算法的最佳情况下的时间复杂度为 \(O(n/m)\)，其中 \(n\) 表示文本串长度，\(m\) 表示模式串长度；而在最坏的情况下，时间复杂度可能达到 \(O(n \cdot m)\)[^2]。尽管如此，在实际应用中 BM 算法通常表现得非常高效。 #### 3. 核心规则详解 ##### （1）坏字符规则 当发现不匹配时，“坏字符”是指当前正在比较但未成功匹配的那个字符。根据此规则，模式串会向右移动到尽可能远的位置，使得模式串中的某个字符能够与文本串中的“坏字符”对齐。 ##### （2）好后缀规则 如果部分匹配失败，则考虑已经匹配的部分作为“好后缀”。基于已知的好后缀位置关系，决定如何调整模式串以继续下一次尝试。 #### 4. Python 实现代码 以下是使用 Python 编写的简化版 Boyer-Moore 字符串匹配函数： ```python def boyer_moore(text, pattern): def build_bad_char_shift(pattern): bad_char = {} for i in range(len(pattern)-1): bad_char[pattern[i]] = i return bad_char def find_good_suffix_shift(pattern): length = len(pattern) suffix = [-1]*length prefix_set = set() for i in reversed(range(length)): prefix_set.add(pattern[i:]) j = i + 1 while j < length and not pattern[j:] in prefix_set: suffix[j] = i j += 1 good_suffix_shift = [0]*(len(suffix)+1) for i in range(len(suffix)): if suffix[i]!=-1: good_suffix_shift[len(pattern)-i]=len(pattern)-suffix[i]-1 return good_suffix_shift bad_char_table = build_bad_char_shift(pattern) good_suffix_table = find_good_suffix_shift(pattern) s = 0 # Shift of the pattern with respect to text while s <= len(text) - len(pattern): shift = 1 mismatched = False for i in range(len(pattern)-1,-1,-1): if text[s+i] != pattern[i]: char_shift = max(1,i-bad_char_table.get(text[s+i],-1)) suffix_shift = good_suffix_table[len(pattern)-(len(pattern)-i)] shift = max(shift,char_shift,suffix_shift) mismatched=True break if not mismatched: return s s += shift return -1 ``` 上述代码实现了完整的 Boyer-Moore 搜索逻辑，包括构建必要的辅助表以及执行具体的匹配操作。 #### 5. 应用场景扩展 除了传统的字符串匹配外，Boyer-Moore 还被应用于更广泛的领域，比如网络安全中的恶意代码检测和防火墙规则匹配等场合[^1]。它凭借出色的性能成为这些高需求环境的理想选择之一。 ---