Boyer-Moore Galil规则

Question

当我了解Boyer-Moore算法时，我正在用Python实现用于子字符串搜索的Galil规则。我在网上搜索过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

备注：

• 如果c不在模式中，偏移量c= -1
• 偏移量c=模式中c的最后一个索引

示例: aaabcb

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

我发现的几个句子说要跟踪第一次错配何时发生在我的内环(j，如果内环内的if -语句是真的话)和我开始比较的位置(在我的例子中，i+j)。我理解我的直觉，我已经检查了其中的所有指数，所以我不应该再做那些比较。我只是不明白如何将这些点连接起来，并达成一个实现。

Answer 1

Galil规则是利用模式中的周期性来减少比较。假设您有一个模式abcabcab。它是周期最小的周期abc。通常，如果存在字符串P，使得P是UUUUU...的前缀，则模式P是周期性的。(在上面的示例中，abcabcab显然是重复字符串abc =U的前缀。)我们将最短的这样的字符串称为P的周期。让这段时间的长度是k (在上面的例子中，k = 3自U = abc以来)。

首先，请记住，只有在文本中出现P之后，Galil规则才适用。当您这样做时，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算法，直到找到另一个匹配。请记住，只有在找到匹配并按k移位时才能使用Galil规则(否则模式不能保证与前面的事件一致)。

现在，您可能想知道，如何确定给定模式的k P。首先需要计算后缀数组N，其中N[i]是前缀P[0, i]和P最长的公共后缀的长度。(您可以通过使用Z算法(例如，如Z )计算P反向的前缀数组这里来计算后缀数组。一旦有了后缀数组，就可以很容易地找到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

Answer 2

@Lajos Nagy的回答完美地解释了Galil规则的概念，但是我们有一种更简单的计算k的方法

只使用KMP算法的前缀函数.

prefix[i]意味着P[0..i]最长的适当前缀，它也是后缀。

还有，k = m-prefix[m-1] .

这篇文章已经解释了细节。