直观地理解Boyer-Moore

Question

我已经研究了StackOverflow上的各种解决方案，试图了解Boyer-Moore算法是如何工作的，但我正在寻找更多-所以为了一步一步地说明该算法是如何工作的(视觉学习对我来说要好得多)。

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

​

​

我更愿意看到它更好地被绘制出来，但如果你能通过伪代码告诉我为什么会发生这种情况，我会很感激。

谢谢。

Answer 1

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

这些步骤可以分解为如下所示，其中我对您的可视化进行了一些修改。

​

​

下面解释了换班步骤

1. Text character a mismatch with pattern character b (不匹配文本字符与模式字符不匹配)。索引为4的字符出现在最后一次出现的表中。移位模式使索引4与不匹配的文本字符a.

对齐

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

1. Text character a mismatch with pattern character b (不匹配文本字符与模式字符不匹配)。索引为4的字符出现在最后一次出现的表中。移位模式使索引4与不匹配的文本字符a.

对齐

1. 文本字符%d与模式字符%b不匹配。Character d未出现在上次出现的表格中。因此，我们可以将整个模式转移到这个不匹配的位置。

1. Text character a mismatch with pattern character b (不匹配文本字符与模式字符不匹配)。索引为4的字符出现在最后一次出现的表中。移位模式使索引4与不匹配的文本字符a.

对齐

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

将模式的索引4与不匹配的文本字符a.对齐

1. 与比较相同的场景

1. 与上述方案相同。

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

1. Text character b
2. pattern character a不匹配。我们到达了文本的末尾，所以我们完成了。