Boyer Moore算法的理解和示例？

Boyer Moore算法的理解和示例？

第一条建议，深吸一口气。您显然会感到压力，当您感到压力时，第一件事就是大脑的大部分区域都关闭了。这使理解变得困难，增加了压力，并且您遇到了问题。

5分钟的超时时间可能无法改善您的顶空，但可能会非常有用。

如此说来，该算法基于简单的原理。假设我要匹配一个length的子字符串

m

。我将首先看一下index上的字符

m

。如果该字符不在我的字符串中，那么我知道我想要的子字符串不能以index处的字符开头

1,2, ... , m

。

如果该字符在我的字符串中，则假定它在字符串的最后位置。然后，我跳回去，开始尝试从可能的起始位置匹配我的字符串。这条信息是我的第一张桌子。

从子字符串的开头开始匹配后，一旦发现不匹配，就不能从头开始。我可能会从另一点开始参加一场比赛。例如，如果我要

anand

在

ananand

成功匹配中进行匹配，请

anan

意识到以下

a

内容不是

d

，但我刚刚进行了匹配

an

，因此我应该跳回去尝试匹配子字符串中的第三个字符。这样，“如果在匹配x个字符后失败，那么我可能在第y个字符上”信息存储在第二个表中。

请注意，当我未能匹配第二张表时，它会根据我刚刚匹配的内容知道匹配的距离。第一张桌子根据我刚刚看到的我不匹配的字符知道我可能要走多远。您想使用这两种信息中较为悲观的信息。

考虑到这一点，算法的工作方式如下：

start at beginning of stringstart at beginning of matchwhile not at the end of the string:    if match_position is 0:        Jump ahead m characters        Look at character, jump back based on table 1        If match the first character: advance match position        advance string position    else if I match:        if I reached the end of the match:FOUND MATCH - return        else:advance string position and match position.    else:        pos1 = table1[ character I failed to match ]        pos2 = table2[ how far into the match I am ]        if pos1 < pos2: jump back pos1 in string set match position at beginning        else: set match position to pos2FAILED TO MATCH