我们已经讲了字符串匹配算法——Horspool算法，小伙伴们有没有学会啊，今天我们要讲的是一个更复杂一点的Boyer-Moore算法。
如果模式最右端的字符和文本中的字符匹配失败，该算法会做出和Horspool算法一样的处理。但是在一个不匹配的字符之前，已经有k (k>0)个字符匹配成功了，这两个算法的处理方式便不一样了。
BM算法有两个移动的表对照，分别是坏符号移动表和好后缀移动表。
坏符号移动
导致这种移动的原因和horspool算法是一样的。如果匹配失败的字符c不在模式中，我们把模式移动到恰好跳过这个字符的位置。可以用公式t1（c）-k来计算移动距离，其中 t1（c）是horspool算法算出来的字符移动表，k是已经成功匹配的字符个数。但是我们显然不想让字符串不移动或者反方向移动，所以在t1（c）-k 为负数或等于0时，向后移动一个位置。
好后缀移动
这一种移动方式是由模式字符串中最后k>0个成功匹配的字符所决定的。我们把模式结尾部分的长度为k的后缀记作suff(k)，在模式中存在另一个suff（k）时，如果以相同字符作为后继我们将模式移动过去是没有意义的 ，因为会出现同样的匹配错误；但不同后继时，我们可以移动从右数第二个suff(k)所在的位置。
事实上，当不存在以不同字符为后继的suff（k）时，我们不能直接移动整个字符串的长度，因为在有些情况下会出错。就像ABCBAB，并且K=3，移动六个字符显然会漏一个匹配的字符串，因为开头的AB与结尾的两个字符相同，而在AB之前没有其他字符串了，这个时候便要考虑一下suff（k）的字串了。
举例来说一下好后缀移动吧，如果字符串"ABCDAB"的后一个"AB"是"好后缀"。那么它的位置是5（从0开始计算，取最后的"B"的值），在"搜索词中的上一次出现位置"是1（第一个"B"的位置），所以后移 4-0=4位，前一个"AB"移到后一个"AB"的位置。
再举一个例子，如果字符串"ABCDEF"的"EF"是好后缀，则"EF"的位置是5 ，上一次出现的位置是 -1（即未出现），所以后移 5-(-1)= 6位，即整个字符串移到"F"的后一位。
def getBMBC(pattern):
# 预生成坏字符表
BMBC = dict()
for i in range(len(pattern) - 1):
char = pattern[i]
# 记录坏字符最右位置（不包括模式串最右侧字符）
BMBC[char] = i + 1
return BMBC
def getBMGS(pattern):
# 预生成好后缀表
BMGS = dict()
BMGS[''] = 0
for i in range(len(pattern)):
# 好后缀
GS = pattern[len(pattern) - i - 1:]
for j in range(len(pattern) - i - 1):
NGS = pattern[j:j + i + 1]
if GS == NGS:
BMGS[GS] = len(pattern) - j - i - 1
return BMGS
def BM(string, pattern):
m = len(pattern)
n = len(string)
i = 0
j = m
indies = []
BMBC = getBMBC(pattern=pattern) # 坏字符表
BMGS = getBMGS(pattern=pattern) # 好后缀表
while i < n:
while (j > 0):
if i + j -1 >= n:
return indies
# 主串判断匹配部分
a = string[i + j - 1:i + m]
b = pattern[j - 1:]
if a == b:
j = j - 1
else:
i = i + max(BMGS.setdefault(b[1:], m), j - BMBC.setdefault(string[i + j - 1], 0))
j = m
# 匹配成功返回匹配位置
if j == 0:
indies.append(i)
i += 1
j = len(pattern)
欢迎关注我们的公众号，学习算法和人工智能知识
