关于字符串匹配BM算法中好后缀的一些细节问题？

Question

关于字符串匹配BM算法中好后缀的一些细节问题想请大家解答一下？

BM算法有坏字符匹配 和 好后缀匹配 ，我的问题在于好后缀匹配 ：在《极x时间》上，看BM算法章节上，说好后缀算法可以单独使用，但我对此抱有疑问，
我认为只用好后缀会错过一些本应该成功的匹配，好后缀不能单独使用，
比如字符串匹配：

主串aabaaaa 匹配串 abaaa ,
第一次匹配 子串aabaa 和 模式串abaaa 时，好字符是aa ，
公共前后椎子串是：模式串前缀子串a, 
所以：模式串a-baaa 对应 子串 aaba-a， 
下一次 从 剩余的aaa 进行匹配 ，不是直接错过了？

Answer 1

感谢邀请，你的理解不对哦，好后缀首先要查找模式串中是否存在该好后缀。

aab-aa-aa 
aba-aa

好后缀为_aa_

其实我们发现 模式串中还存在其他_aa_子串

所以下一次移动是这样的

aab-aa-aa
 ab-aa-a

最大公共前后缀移动，是在模式串中子串不存在其他好后缀的情况下使用的。

提出两种方法是因为你不知道当前用哪种方法复杂度更优秀，所以每次都会比较两者的移动距离，选用移动距离更远的一个。

两种方法都能单独使用。

好后缀算法的移动规则：

先查找模式串中是否存在非后缀(模式串中)的好后缀子串，如果存在，则将模式串中最右边的该子串[非后缀(模式串中)的好后缀子串]与主串中好后缀对齐，如果不存在，则查找最长公共前后缀，将模式串移动到前缀最长匹配的位置，没有公共前后缀则直接将模式串移动到好后缀后一位。