博耶-摩尔加利尔规则

Question

当我了解Galil Rule时，我正在为 Python 中的子字符串搜索实现Boyer-Moore 算法。我在网上四处寻找 Galil 规则，但除了几句话我什么也没找到，而且我无法访问原始论文。如何将其实现到我当前的算法中？

i = 0
while i < (N - M + 1):
    skip = 0
    for j in reversed(range(0, M)):
        if pattern[j] != text[i + j]:
            skip = max(1, j - offsets[text[i+j]])
            break
    if skip == 0:
        return i
    i += skip
return -1

笔记：

• offsets[c] = -1 如果 c 不在模式中
• offsets[c] = 模式中 c 的最后一个索引

示例：aaabcb

• 偏移[a] = 2
• 偏移[b] = 5
• 偏移[c] = 4
• 偏移[d] = -1

我发现的几句话说要跟踪我的内部循环中第一次不匹配发生的时间（j，如果内部循环中的 if 语句为 True）以及我开始比较的位置（i + j，在我的情况下）。我理解我已经检查了这些之间的所有索引的直觉，所以我不应该再次进行这些比较。我只是不明白如何连接点并实现实现。

Answer 1

Galil 规则是关于利用模式中的周期性来减少比较。假设你有一个模式abcabcab。它是周期性的，周期最小abc。一般来说，P如果有一个字符串的前缀为U，P则模式是周期性的UUUUU...。（在上面的例子中，abcabcab显然是重复字符串abc=的前缀U。）我们称最短的这样的字符串为句点P。让那个时期的长度为k（在上面的例子中，k = 3因为U = abc）。

首先，请记住，Galil 规则仅在您发现P文本中出现的 之后才适用。当你这样做时，Galil 规则说你可以移动k（模式的周期性）并且你只需要比较k现在移动的模式的最后一个字符来确定是否有匹配。

下面是一个例子：

P = ababa
T = bababababab
U = ab
k = 2

第一次出现：b[ababa]babab。现在你可以k = 2切换，你只需要检查模式的最后两个字符：

T = bababa[ba]bab
P =    aba[ba]       // Only need to compare chars inside brackets for next match.

其余部分P 必须匹配，因为 P 是周期性的，并且您将它k 从现有匹配（这很关键）中按其周期移动，因此重复部分将很好地排列。

如果您找到另一个匹配项，请重复。但是，如果发现不匹配，则将恢复到标准的 Boyer-Moore 算法，直到找到另一个匹配。请记住，您只能在找到匹配项并移动时使用 Galil 规则k（否则模式不能保证与前一次匹配）。

现在，您可能想知道如何确定k给定的模式P。您需要先计算后缀数组N，其中N[i]将是前缀P[0, i]和的最长公共后缀的长度P。（您可以通过计算前缀阵列计算后缀阵列Z上反向的P使用Z算法，如所描述这里，例如。）一旦你的后缀数组，你可以很容易找到k，因为这将是最小的k > 0，使得N[m - k - 1] == m - k（在哪里m = |P|）。

例如：

P = ababa
m = 5
N = [1, 0, 3, 0, 5]
k = 2  because  N[m - k - 1] == N[5 - 2 - 1] == N[2] == 3 == 5 - k