Boyer-Moore 算法

定义

Boyer-Moore 算法是 Robert Boyer 与 J Strother Moore 于 1977 年提出的字符串匹配算法,以从右向左比较和大幅度跳跃著称,是许多文本搜索工具的核心。

原理

算法对齐模式串与文本后,从模式串末尾向前比较。失配时按两条规则取较大的移动距离:坏字符规则根据文本中失配字符在模式串中最后出现的位置决定右移量;好后缀规则利用已匹配的后缀在模式串中的其他出现位置决定右移量。文本越长、字符集越大,平均跳过的字符越多,最好情况接近 O(n/m)。

应用

grep 等文本搜索工具、编辑器查找功能广泛采用其思想;简化变体 Boyer-Moore-Horspool 只用坏字符规则,实现更简单。

优缺点

实际平均速度快于 KMP;但预处理表构造较复杂,最坏情况性能需要额外规则保证。