1. 什么是BM算法
1977 年,德克萨斯大学的 Robert S. Boyer 教授和 J Strother Moore 教授发明了一种新的字符串匹配算法：Boyer-Moore 算法,简称 BM 算法. 该算法 从模式串的尾部开始匹配,且拥有在最坏情况下 O(N) 的时间复杂度.有数据表明,在实践中,比 KMP 算法的实际效能高,可以快大概 3-5 倍.
BM算法的一个特点是当不匹配的时候一次性可以跳过不止一个字符. 即它不需要对被搜索的字符串中的字符进行逐一比较,而会跳过其中某些部分.通常搜索关键字越长,算法速度越快. 它的效率来自于这样的事实：对于每一次失败的匹配尝试,算法都能够使用这些信息来排除尽可能多的无法匹配的位置.
2. 坏字符规则（bad-character shift）
在 BM 算法中,模式串中的字符跟主串进行匹配的时候是由后向前进行匹配,对于上图来说最先比对的是模式串中的 d 发现和主串中的 c 不相等,那么此时主串中的 c 就叫做坏字符
2.1 坏字符
坏字符坏字符模式串ii = 2模式串2.2 模式串移动
模式串模式串坏字符从后向前k 默认值为 -1 表示没有找到模式串i - k坏字符c模式串坏字符模式串此时模式串需要向后移动 i - k 位 2 - 0 = 2 位,匹配成功
3. 好后缀规则（good-suffix shift）
3.1 好后缀
主串模式串好后缀从后向前3.2 模式串的移动(第1种情况)
模式串从后向前好后缀好后缀那么如果说模式串中没有与好后缀一样的字符串该怎么办呢？
在讲述之前需要先了解几个概念帮助后续的理解分别是
模式串好后缀后缀子串模式串好后缀前缀子串3.3 模式串的移动(第2种情况)
好后缀的子串模式串的前缀子串好后缀好后缀子串模式串前缀模式串的移动(第1种情况)模式串好后缀好后缀好后缀子串模式串的前缀子串模式串中前缀子串好后缀模式串坏字符规则好后缀规则坏字符规则好后缀规则取较大向后移动位数5. Golang BM 算法代码实现
Go语言标准库中里在 strings/search.go 里使用了Boyer-Moore字符串搜索算法
The End
ssh $用户@mojotv.cnssh mojotv.cn hn