algorithm - Boyer Moore算法的理解和例子？

Question

我在理解 Boyer Moore 字符串搜索算法时遇到问题。

我正在关注以下文档。 Link

我无法弄清楚 delta1 和 delta2 在这里的真正含义是什么，以及他们如何应用它来查找字符串搜索算法。 语言看起来有点模糊..

如果有人能帮助我理解这一点，那将非常有帮助。

或者，如果您知道任何其他易于理解的链接或文档，请分享。

提前致谢。

Answer 1

Boyer-Moore 背后的见解是，如果您开始在以模式中的last 字符开头的字符串中搜索模式，则当遇到不匹配时，您可以将搜索向前跳转多个字符.

假设我们的模式 p 是字符序列 p1, p2, ..., pn我们正在搜索字符串 s，当前与 p 对齐，以便 pn 位于 i 中的索引 >s.

例如:

s = WHICH FINALLY HALTS.  AT THAT POINT...
p = AT THAT
i =       ^

B-M 论文提出了以下观察结果:

(1) 如果我们尝试匹配一个不在 p 中的字符，那么我们可以向前跳转 n 个字符:

'F' 不在 p 中，因此我们前进 n 个字符:

s = WHICH FINALLY HALTS.  AT THAT POINT...
p =        AT THAT
i =              ^

(2) 如果我们尝试从 p 的末尾匹配一个最后位置为 k 的字符，那么我们可以向前跳转 k 个字符:

' 在 p 中的最后位置是从末尾算起 4，因此我们前进 4 个字符:

s = WHICH FINALLY HALTS.  AT THAT POINT...
p =            AT THAT
i =                  ^

现在我们从 i 开始向后扫描，直到我们成功或遇到不匹配。 (3a) 如果不匹配从 p 开始出现 k 个字符并且不匹配的字符不在 p 中，那么我们可以前进(在至少)k 个字符。

'L' 不在 p 中并且与 p6 不匹配，因此我们可以(至少)前进 6 个字符:

s = WHICH FINALLY HALTS.  AT THAT POINT...
p =                  AT THAT
i =                        ^

然而，我们实际上可以做得比这更好。 (3b) 因为我们知道在旧的 i 中我们已经匹配了一些字符(在本例中为 1)。如果匹配的字符不匹配p的开头，那么我们实际上可以向前跳多一点(这个额外的距离在论文中称为'delta2'):

s = WHICH FINALLY HALTS.  AT THAT POINT...
p =                   AT THAT
i =                         ^

此时，观察 (2) 再次适用，给出

s = WHICH FINALLY HALTS.  AT THAT POINT...
p =                       AT THAT
i =                             ^

宾果游戏!我们完成了。