当匹配失败时，根据前缀函数快速跳过已匹配的部分，避免重复比较

Boyer-Moore算法和KMP（Knuth-Morris-Pratt）算法都是用于字符串匹配的经典算法，但它们在实现思路、时间复杂度和适用场景上存在显著差异。以下是两者的主要区别：

1. 核心思想

KMP算法：

前缀函数（Partial Match Table）：通过预处理模式串，构建一个部分匹配表（前缀函数），记录模式串中每个位置的最长相等前后缀长度。

利用已匹配信息：当匹配失败时，根据前缀函数快速跳过已匹配的部分，避免重复比较。

Boyer-Moore算法：

坏字符规则（Bad Character Rule）：当匹配失败时，根据模式串中字符的最后出现位置，决定模式串向右移动的距离。

好后缀规则（Good Suffix Rule）：当匹配失败时，根据已匹配的后缀部分，决定模式串向右移动的距离。

从右向左匹配：Boyer-Moore算法从模式串的末尾开始匹配，而不是从开头。

2. 时间复杂度

KMP算法：

预处理时间：O(m)，其中m是模式串的长度。

匹配时间：O(n)，其中n是文本的长度。

总时间复杂度：O(n + )。

Boyer-Moore算法：

预处理时间：

坏字符规则：O(m + σ)，其中σ是字符集大小（如ASCII字符集大小为256）。

好后缀规则：O(m)。

匹配时间：最坏情况下为O(nm)，但在实际应用中通常接近O(n/m)。

总时间复杂度：最坏情况下O(nm)，但平均情况下表现优于KMP。

3. 空间复杂度

KMP算法：

需要一个大小为m的数组来存储前缀函数，因此空间复杂度为O(m)。

jrhz.info

Boyer-Moore算法：

需要两个数组（坏字符表和好后缀表），空间复杂度为O(m + σ)。

如果字符集σ较小（如ASCII字符集），空间复杂度可以近似为O(m)。

4. 适用场景

KMP算法：

适用于文本较短或模式串较长的场景。

当需要高效处理多个模式串时，KMP算法的前缀函数可以复用。

Boyer-Moore算法：

适用于文本较长且模式串较短的场景。

在实际应用中，Boyer-Moore算法通常比KMP算法更快，尤其是在文本远大于模式串时。

5. 实现难度

KMP算法：

实现相对简单，逻辑清晰，易于理解。

核心在于前缀函数的构建和使用。

Boyer-Moore算法：

实现较为复杂，尤其是好后缀规则的实现。

需要处理坏字符规则和好后缀规则的优先级问题。

6. 匹配方向

KMP算法：

从左到右匹配。

Boyer-Moore算法：

从右到左匹配。

总结对比

特性 KMP算法 Boyer-Moore算法

核心思想 前缀函数 坏字符规则 + 好后缀规则

时间复杂度 O(n + m) 最坏O(nm)，平均接近O(n/m)

空间复杂度 O(m) O(m + σ)

适用场景 文本较短或模式串较长 文本较长且模式串较短

实现难度 较低 较高

匹配方向 从左到右 从右到左

选择建议

如果文本较短或模式串较长，KMP算法是更好的选择。

如果文本较长且模式串较短，Boyer-Moore算法通常表现更优。

在实际应用中，Boyer-Moore算法及其变种（如Boyer-Moore-Horspool）更为常用，因为它们在大多数情况下性能更优。

希望这些信息能帮助你更好地理解两种算法的区别！