04. Boyer Moore 算法

[giscus[bot]]

04. Boyer Moore 算法

Boyer Moore 算法 1. Boyer Moore 算法介绍 Boyer Moore 算法：简称为 BM 算法，是由它的两位发明者 Robert S. Boyer 和 J Strother Moore 的名字来命名的。BM 算法是他们在 1977 年提出的高效字符串搜索算法。在实际应用中，比 KMP 算法要快 3~5 倍。 BM 算法思想：对于...

https://algo.itcharge.cn/06.String/02.String-Single-Pattern-Matching/04.String-Boyer-Moore/

[Yiniau]

generageGoodSuffixList 的 16-18

while j < m - 1 - i:
    if gs_list[j] == m:
        gs_list[j] = m - 1 - i 
    j += 1

为什么要做这样一个循环赋值？

[Yiniau]

再问个情况，对于模式串 p = 'abcxabc' 如果在 j = 5 时失配，按照好后缀规则，不是应该让 p[3] = c 的这个位置和 j 对齐吗？按照代码跑出来，suffix[5] 时要移动 7 个位置

[FELMoKnight]

有个小问题，应该是这样的：
情况 1：模式串中有子串匹配到好后缀，条件为 p[0...i-1] == p[m-1-(i-1)...m-1]。
情况 2：模式串中有最长前缀匹配到好后缀，条件为 p[i-(s-1)...i] == p[m-1-(s-1)...m-1]。

[ivyinautumn]

你的理解有误
  针对情况1：以文章里的2.2 好后缀规则里情况1的模式串"ABCDEFGBCDE"为例，此时坏字符为"G"，好后缀为"BCDE"。该模式串中的子串"BCDE"出现了两次，符合情况1要求，但出现在前面的"BCDE"并不是从下标0开始的。也就是说情况1只要求好后缀必须整体出现在坏字符的前面，并非像你描述的条件等式左侧那样$p[0...i-1]$从0开始。对应的正确描述应是$p[i-s...i] == p[m-1-s...m-1]$，此处$s$是好后缀长度，而$i$则应是出现在坏字符左侧(若好后缀重复出现，则取最右侧的$i$)。

  针对情况2：以"example"为例，当坏字符为$a$时，则好后缀为"mple"(整体)，而"ple"，"le"，"e"这三个也是好后缀(部分)。此时"mple"在坏字符前面没有出现过，然后从字符串开始处(下标0开始)按长度由大到小顺序依次检索上面三个部分好后缀，发现只有"e"出现在开始处，则根据情况2此时移动距离为好后缀在模式串中的位置-最长前缀在模式串中的位置 = 6 - 0 = 6，所以你的条件描述等式左侧有问题，应当从0开始，即$p[0...s] == p[m-1-s...m-1]$，此处$s$为好后缀部分出现在模式串开始处最长的那一个的长度。

[FELMoKnight]

你说的是正确的。我才发现我把两种情况弄反了。我想说的是从0到i长度并非i，而是i+1；同样的，从i-s到i长度并非s，而是s+1。