java - Boyer-Moore 字符串搜索算法起始对齐

Question

我不是专业程序员，所以请多多包涵。我正在四处寻找为什么 haystack 和 needle 的初始“对齐”不应该在 needle 的最后一个字符与 haystack 中的相同字符的第一次一致时进行，但最早 在 needle.length()-1 处寻找，而不是在 'haystack.needle.length()-1' 和 'needle.length()-1' 处强制比较？

例子:-

干草堆:actuateaaaaaat

针头:下降

以上，在 haystack 中最后一个 't' 之前的所有内容都可以完全忽略，就移位和比较而言。

Answer 1

如果您要尝试在大海捞针中找到第一个 t(从第七个字符开始)，您将不得不查看大海捞针中的每个字符，直到最后。

Boyer Moore 找到了更少比较的位置。比如比较t和e后，可以向前移动五个字符。所以下一次比较将在 t 和倒数第二个 a 之间进行，这将导致位移为二。因此，仅经过两次比较(而不是七次)就可以找到正确的对齐方式。