Boyer和Moore算法,移位表计算

Question

我整晚都没能为搜索词"anabanana"计算一个简单的移位表,用于Boyer和Moore模式匹配算法.

我找到了以下示例,没有任何解释:

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

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。

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