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

Question

我整个晚上都没能为搜索词“anabanana”计算一个简单的转换表，以便在 Boyer and Moore pattern matching algorithm 中使用。 .

我在没有任何解释的情况下找到了以下示例:

有谁能帮我理解和解释图像的查找移位表的方法吗？

Answer 1

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

“Wort”行是您正在分析的模式，(在我看来)没有必要考虑上面的“Text”行。相反，假设有一个额外的行包含模式中从左到右的字符从零开始的位置。 长度m图案的p[]描绘的是9。 下面每一行我命名为 p_i[]其中 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 .

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