当我了解到Boyer-Moore Algorithm时，我正在Python中实现Galil Rule的子字符串搜索我在网上到处寻找加利尔规则，但除了几句话，我什么也没找到，而且我也找不到原始文件如何将其实现到当前算法中？
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）。我明白直觉，我已经检查了所有的指数，所以我不应该再做这些比较。我只是不明白如何把这些点联系起来并最终实现。
最佳答案
galil规则是利用模式中的周期性来减少比较。假设你有一个模式abcabcab。它是周期性的，周期最小一般来说，如果字符串abc是P的前缀，则模式U是周期性的。（在上面的例子中，P显然是重复字符串UUUUU...=abcabcab的前缀）我们称最短的字符串为abc的周期设该周期的长度为U（在上面的示例中，从P开始）。
首先，请记住，galil规则仅在您在文本中找到k的出现之后才适用。当您这样做时，Galil规则说您可以按k = 3（模式的周期性）移动，并且您只需要比较现在移动的模式的最后U = abc个字符就可以确定是否存在匹配。
下面是一个例子：
P = ababa
T = bababababab
U = ab
k = 2
第一次出现：
P现在您可以按k移动，只需检查模式的最后两个字符：T = bababa[ba]bab
P = aba[ba] // Only need to compare chars inside brackets for next match.
其余的
k必须匹配，因为P是周期性的，并且你从它的周期b[ababa]babab从现有的匹配中转移（这是至关重要的），所以重复的部分将很好地排队。如果你找到另一个匹配的，就重复一遍。但是，如果发现不匹配，则返回标准的boyer-moore算法，直到找到另一个匹配。请记住，只有在找到匹配项并按
k = 2移动时才能使用galil规则（否则模式不能保证与上一个匹配项对齐）。现在，您可能想知道，如何确定给定模式的
P。首先需要计算后缀数组k，其中k是前缀k和P的最长公共后缀的长度。（例如，您可以通过使用z算法计算N背面的前缀数组N[i]来计算后缀数组，如here所述。）拥有后缀数组后，您可以轻松找到P[0, i]，因为它是最小的P，因此Z（其中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