algorithm - Boyer 和 Moore 算法，移位表计算

Question

我整个晚上都没能计算出一个简单的移位表，用于搜索用于Boyer 和 Moore 模式匹配算法的搜索词“anabanana” 。

我发现以下示例没有任何解释：

任何人都可以帮助我理解和解释图像查找班次表的方法吗？

Answer 1

我想我明白这里做了什么，所以我会试着解释一下。

“Wort”行是您正在分析的模式，（在我看来）不需要考虑上面的“Text”行。相反，假设在您的模式中从左到右包含从零开始的字符位置的附加行。所描绘m的图案的长度是 9。下面的每一行 I 命名其中 i 是右侧的索引p[]p_i[]

进一步的解释基于2：

在模式下方的下排标记与上述模式中的字符匹配的所有字符。（在这里划掉）

for i=1 to m do
    search in the rows below for a subpattern where p[m-i]<>p_j[m-1] (*)
    and p[m-i+1, ..., m-1]=p_j[m-i+1, ..., m-1]
    index j is your shift value for shift[i]
od  

(*) 注意：当移位的模式p_j向右移动太远时，将有空字符进行比较。在这种情况下，您可以随时假设==或<>根据需要。始终使用所有可能的最小值j。

我希望这会有所帮助，尽管有点晚了。