algorithm - Boyer-Moore 字符串匹配 - 良好的后缀移位

Question

我了解坏符号表。在好的后缀表中，距离不应该计算为从最右边出现的模式到模式文本末尾的距离吗？在这种情况下，下表中的所有距离 (d2) 是否不应该都为 1(最后一个条目除外，该距离为 5)，因为紧邻其左侧的模式将可用？

类似地，也从未理解下表。有什么帮助吗？

引用:

问题 - 第 6 页，问题 7。

---

答案 - 第 11 页

---

计算机算法的设计与分析- Anany Levitin ( https://umutzafer.files.wordpress.com/2012/01/solu7.pdf )

文本 - The design and analysis of computer algorithms- Anany Levitin (第263页)

Answer 1

好的后缀规则是寻找已经匹配的后缀实例，其中前一个字符不同。例如，在第一个表中的“好后缀”00 的情况下，移位会查找前面没有 0 的 00 实例。 。

为什么？因为我们知道“好后缀”前面的 0 不匹配；否则我们就不会尝试转变。

在第二个表中，找不到这样的实例。因此，我们会寻找与“好后缀”的后缀相匹配的模式的合理前缀。