Boyer-Moore算法

算法

Boyer-Moore算法是一种高效的字符串搜索算法,它通过从右向左比较并利用坏字符和好后缀两种规则来跳过不必要的比较,实现比朴素算法更快的搜索速度。

算法讲解

Boyer-Moore 算法

介绍

Boyer-Moore算法是一种高效的字符串匹配算法,由 Robert S. Boyer和J Strother Moore 设计于1977年。它从右向左比较字符,并利用两个启发式规则(坏字符规则和好后缀规则)在不匹配情况下实现较大跳跃,减少比较次数。Boyer-Moore算法在实际应用中大部分情况下比朴素算法和KMP算法更高效。

算法步骤

  1. 预处理模式串,构建坏字符表和好后缀表
  2. 将模式串对齐到文本串的开始位置
  3. 从模式串的最右侧字符开始比较,从右向左进行匹配
  4. 如果发生不匹配,通过以下规则计算跳转距离:
    • 坏字符规则:根据不匹配字符在模式串中的最右位置决定跳转距离
    • 好后缀规则:根据已匹配部分在模式串中的重复情况决定跳转距离
  5. 选择两个规则中的最大跳转距离,移动模式串
  6. 重复步骤3-5,直到找到匹配或到达文本串末尾

核心特性

  • 从右向左比较:与大多数字符串匹配算法不同,从模式串的末尾开始比较
  • 双规则跳转:利用坏字符规则和好后缀规则计算跳转距离
  • 时间复杂度:最坏情况O(m*n),m是模式串长度,n是文本串长度;平均情况接近O(n/m)
  • 空间复杂度:O(k+m),其中k是字符集大小,m是模式串长度
  • 适用范围:特别适合长模式串和大字符集场景

...