从对齐窗口的右端开始

先把模式放在一个可能文本起点上,从模式最后一个字符向左比较。如果某个位置失配,算法不一定只把起点加一,而是利用已经知道的字符关系,推导下一次仍有机会成立的对齐位置。

若全部字符匹配,就得到一次出现;若跳过多个起点,正确性要求这些位置确实不可能匹配。速度收益来自有根据地排除候选,而不是忽略字符检查后仍默认结果正确。

参考:[1]

坏字符与好后缀提供不同信息

坏字符规则考察造成失配的文本字符在模式中的位置。Princeton示例预存每个字符最靠右的出现位置,失配后据此计算移动量,至少前进一格;若该字符根本不在模式中,常能一次跳过更多候选。

好后缀规则则利用已经匹配的模式尾部,寻找它在模式其他位置的兼容出现或与前缀的重叠。两条规则使用不同证据。教材提供的BoyerMoore.java只实现坏字符部分,明确没有实现强好后缀规则。

参考:[1] [2] [3]

重复文本与实现边界

许多普通文本上,跳跃会使实际检查的字符数量显著减少,但仅坏字符版本仍有差的最坏输入,重复模式尤其需要小心。不能把“常常跳得远”直接写成任何输入上都只需次线性工作,或者给简化代码套用别的增强版本的界限。

预处理表需要覆盖实际字符集合,数组固定为256的示例也不是对任意Unicode字符都可直接索引。比较算法时,应说明规则组合、编码、是否报告全部重叠命中,以及预处理是否能在多次搜索之间复用。

参考:[2] [1]