在 Boyer-Moore 算法中,您从模式末尾开始将模式字符与文本字符进行比较。如果您发现不匹配,则您拥有该类型的配置
....xyzabc.... <-text
....uabc <- pattern
^
mismatch
Now the 不良性格转变表示移动模式,以便不匹配的文本字符与模式初始部分中最后一次出现的该字符对齐(模式减去最后一个模式字符)(如果存在这样的情况),或者与模式之前的一个位置对齐如果不匹配的字符根本没有出现在模式的初始部分。
如果情况是这样的话,这可能会向左移动
v
...xyzazc...
....uazc
..uazc
因此,仅凭这一点并不能保证取得进展。
另一个转变,好的后缀移位,对齐文本的匹配部分,m
,该字符序列在模式中最右边出现的位置与匹配的后缀不同,该字符前面有一个不同的字符(如果匹配的后缀也是模式的前缀,则不包含任何字符)m
模式的 - 如果发生这种情况。
例如
v
....abcdabceabcfabc...
...xabcfabcfabc
...xabcfabcfabc
会导致后缀良好地移动四个位置,因为匹配的部分m = abcfabc
出现在模式中其后缀出现左侧的四个位置,并且前面有一个不同的字符 (x
代替f
) 比后缀位置。
如果模式中没有完全出现前面有与后缀不同的字符的匹配部分,则良好的后缀移位会将文本的匹配部分的后缀与模式的前缀对齐,选择最大重叠,例如
v
...robocab....
abacab
abacab
好的后缀移位总是将模式向右移动,因此保证了进展。
然后,在每次不匹配时,比较坏字符移位和好后缀移位的进展,并选择较大者。 Christian Charras 和 Thierry Lecroq 对其进行了更深入的解释here http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140,以及许多其他字符串搜索算法。
对于您在评论中提到的示例,
SSIMPLE EXAMPLE
EXAMPLE
^
匹配的后缀是MPLE
,不匹配的文本字符是I
。所以坏字符移位会寻找最后一次出现的I
在模式的初始部分。没有,因此错误的字符转换会改变模式,从而导致不匹配I
是模式开始之前的一个
SSIMPLE EXAMPLE
EXAMPLE
好的后缀移位会寻找最右边出现的MPLE
在图案中not前面有一个A
,或最长的后缀MPLE
这是模式的前缀。模式中的匹配部分在后缀之前没有完全出现,因此匹配部分的最长后缀(同时也是模式的前缀)决定了良好的后缀移位。在这种情况下,匹配部分的两个后缀(即模式的前缀)是单字符串E
和空字符串。最长的显然是非空字符串,所以好的后缀移位对齐单字符后缀E
在文本的匹配部分与模式的单字符前缀
SSIMPLE EXAMPLE
EXAMPLE
好的后缀移位会将模式进一步向右移动,因此这就是所选的移位。
然后在最后一个模式位置立即出现不匹配,然后错误的字符移位与P
在文本中与P
在模式中(如果不匹配发生在最后一个模式字符处,则根本不需要考虑好后缀移位,因为在这种情况下,它永远不会产生比坏字符移位更大的移位)。
然后我们就有了完整的比赛。
在带有图案的变体中TXAMPLE
,好的后缀移位发现匹配部分的非空后缀没有一个是模式的前缀(并且模式中没有出现完整的匹配部分not之前是A
),所以好的后缀移位会对齐文本匹配部分的空后缀(E
和空格)以及模式的空前缀(前面的空字符串T
), 导致
SSIMPLE EXAMPLE
TXAMPLE
(然后在下一步中,坏字符移位将两个字符对齐L
s,此后步骤中的下一个不匹配发生在初始位置T
的模式)。