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

Question

我明白这个坏符号的桌子。在好后缀表中，不应该将距离计算为从模式的最右边出现到模式文本末尾的距离吗？在这种情况下，下面的表不应该将所有距离(d2)都设为1(除了最后一个条目为5)，因为同样的模式将可用在它的左端？

​

​

在类似的条件下，也永远不懂下表。有什么帮助吗？

​

​

参考资料：

问题-第6页，问题7。

答覆-第11页

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

文本- 计算机算法的设计与分析& Anany Levitin (第263页)

Answer 1

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

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

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

Answer 2

有时候，书中没有像您希望的那样在这种类型的算法中显式地提到事物，问题是，查找与不同的前面字符匹配的部分的出现也意味着完全没有前面的字符--在模式01010中是这样的，在模式01010中，当k=1 0在索引0处的dist之间没有1(实际上没有任何内容)和0之间的匹配项和前面的1是D2=4时。

当找到匹配部分的k=1后缀0作为前缀，从索引0开始，且两者之间的距离为4 so D2=4时，当k=3我们匹配的部分前面有1时，我们会看到另一个010从索引0开始，没有任何计数，它们之间的距离是2 so D2=2。最后，当匹配部分的k=4后缀010位于索引0，它与后缀010的距离为2时，D2再次为2。