algorithm - 从视觉上理解 Boyer-Moore

Question

我已经研究过 StackOverflow 上的各种解决方案，试图了解 Boyer-Moore 算法的功能，但是我正在寻找更多关于算法实际功能的分步说明（视觉学习对我来说要好得多）。

我试图理解这张图片，但我不完全理解为什么在比较 6 中它会向前跳过：

我希望看到它画得更好，但如果你能通过伪代码告诉我为什么会发生这种情况，我将不胜感激。

谢谢你。

标签： algorithmboyer-moore

Answer 1

Boyer Moore 算法中最重要的是最后出现表，它是模式的预处理。它存储模式中每个不同字符出现的最后一个索引。

这些步骤可以分解如下所示，我在其中稍微修改了您的可视化。

移位步骤解释如下

1. 文本字符a与模式字符b不匹配。字符a出现在索引为 4 的最后一个出现表中。移位模式使索引 4 与不匹配的文本字符a对齐。

2. 文本字符a与模式字符c不匹配。字符a出现在索引为 4 的最后一个出现表中。移动模式以使索引 4 与不匹配的文本字符a对齐将使模式向后移动。这没有意义，所以我们所能做的就是将模式移动 1。

3. 文本字符a与模式字符b不匹配。字符a出现在索引为 4 的最后一个出现表中。移位模式使索引 4 与不匹配的文本字符a对齐。

4. 文本字符d与模式字符b不匹配。字符d未出现在最后一个出现表中。因此，我们可以将整个模式转移到这种不匹配之外。

5. 文本字符a与模式字符b不匹配。字符a出现在索引为 4 的最后一个出现表中。移位模式使索引 4 与不匹配的文本字符a对齐。

6. 所有字符都匹配，即我们有一个完全匹配。将模式天真地移动 1。

7. 与比较 7 相同的情况。将模式的索引 4 与不匹配的文本字符a对齐。

8. 与上述相同的场景。

9. 与比较 2、3 和 4 完全相同的情况。将模式移位 1。

10. 文本字符b与模式字符a不匹配。我们到了文本的结尾，所以我们完成了。