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

Question

我不是一个专业的程序员，所以请容忍我。我四处看看为什么大海捞针和针头的初始“对齐”不应该是在大海捞针的最后一个字符的第一次和大海捞针中的相同字符的第一次一致，而是最早在needle.length()-1，而不是在'haystack.needle.length()-1‘和'needle.length()-1’中进行比较？

例子:-

干草堆

针头:下垂

上面，在大海捞针之前的一切都可以被完全忽略，从之前的变化和比较来看。

Answer 1

如果你想在干草堆中找到第一个t (从第七个字符开始)，你必须查看干草堆中的每个字符，直到最后。

博耶·摩尔( Boyer )发现这一职位的比较要少得多。例如，在比较了t和e之后，它可以向前移动五个字符。下一个比较是t和第二个a，这将导致两个位移。因此，经过两次比较，而不是七次比较，就可以找到正确的对齐方式。