100种算法【Python版】第38篇——Boyer-Moore算法

1 算法说明

Boyer-Moore算法由Robert S. Boyer和J. Strother Moore于1977年提出，旨在提高字符串匹配的效率。该算法在寻找固定模式的过程中，利用模式本身的信息，优化搜索过程，特别适合长文本中的模式查找。

算法原理
Boyer-Moore算法的核心思想是，当模式与文本不匹配时，可以利用模式中已匹配字符的信息，快速跳过不必要的比较，而不是逐字符地移动模式。它主要依赖于两个主要规则：

• 坏字符规则：当遇到不匹配时，将模式向右移动，使得文本中出现的坏字符与模式中最后出现的字符对齐。
• 好后缀规则：如果在模式中已经匹配的后缀部分出现了，则可以根据该后缀的信息决定模式的移动。

算法步骤

• 预处理模式：
  • 生成坏字符表：记录模式中每个字符最后出现的位置。
  • 生成好后缀表：记录模式中每个后缀的匹配信息。
• 搜索过程：
  • 从文本的起始位置开始，将模式与文本进行比较。
  • 如果匹配成功，继续比较下一个字符；如果不匹配，则根据坏字符规则和好后缀规则决定模式的移动。