BM 算法图解
BM 算法原理
BM 算法分为两部分
- 坏字符规则
- 好后缀规则
将这两大规则结合使用就能高效的完成字符串匹配，在讲述这 2 个规则前先了解几个概念
主串与模式串
如图我们需要在字符串 abcacabdc 中查找是否存在 cbd 这个字符串，那么 abcacabdc 就叫做称作主串，cbd 就是模式串
坏字符规则
在 BM 算法中，模式串中的字符跟主串进行匹配的时候是由后向前进行匹配，对于上图来说最先比对的是模式串中的 d 发现和主串中的 c 不相等，那么此时主串中的 c 就叫做坏字符
坏字符
模式串中第一个跟主串不相等的字符（模式串倒序匹配），叫做坏字符（主串字符）
此时坏字符就是主串中的 c
此时我们将坏字符对应模式串的字符的位置，记作 i，那么此时 i = 2
虽然我们将模式串倒序匹配，但是模式串本身的位置不做更改即 a b d 分别对应下标 0 1 2
模式串移动
那么此时模式串该向后移动几位呢，做法是这样的，从模式串中查找坏字符的位置（从后向前找找到第一个匹配的就停下来）记作 k 默认值为 -1 表示没有找到，然后将模式串向后移动 i - k 位
此时通过坏字符 c 去模式串 abd 中查找发现没有找到，那么 k = -1，此时移动 2 - (-1) = 3 位，如下
此时坏字符是 a 对应的模式串中字符的位置仍然是 2，继续从模式串中查找坏字符，找到了 k = 0
此时模式串需要向后移动 i - k 位 2 - 0 = 2 位，匹配成功
好像坏字符规则就能满足高效匹配了，还要好后缀规则做什么？
来看下如下场景，主串不变，假设模式串为 dbca，那么此时坏字符对应模式串中的位置 i = 0，模式串中包含了坏字符 k = 3，那么模式串该向后移动 i - k = 0 - 3 = -3 位，可以看到这时候需要向前移动了，就出错了，所以单凭坏字符规则是不行的还需要结合好后缀规则
好后缀规则
对于主串和模式串来说存在相等的串就是好后缀
模式串的移动-1
在模式串中寻找，是否还有与好后缀一样的字符串，如果有的话将其向后移动到之前好后缀的位置，如下
那么如果说模式串中没有与好后缀一样的字符串该怎么办呢？
在讲述之前需要先了解几个概念帮助后续的理解分别是
- 好后缀的后缀子串
- 模式串的前缀子串
好后缀的后缀子串
假设模式串为 bccabc 此时的好后缀为 abc 那么它的后缀子串分别是
- bc
- c
模式串的前缀子串
假设模式串为 bccabc 此时的好后缀为 abc 那么它的前缀子串分别是
- bc
- b
模式串移动-2
在计算好后缀的子串与模式串的前缀子串的时候，长度保存一致才有意义，比如好后缀为 abc 三位，它的后缀子串最多为 2 位，那么求模式串好前缀的时候也只需要至多取前 2 位就可以了。
因为取 3 位的话就是 模式串移动-1 的模式串中还有另外的与好后缀相等的情况了。如果超过 3 位的话匹配就没有意义了
此时好后缀 abc 的后缀子串 bc 正好跟模式串的前缀子串 bc 一致，那么就将模式串中前缀子串移动到好后缀的 bc 处，如下
此时在模式串 bccabc 中找到了 bc ，然后将其移动到当前位置最终匹配成功，如果最后一个字符还不相等意味着匹配失败，没有找到。
如何选择是使用坏字符规则还是好后缀规则来进行字符串匹配
如前文，坏字符规则有缺陷可能导致向前移动，好后缀规则可以正常使用。
在进行匹配算法的时候，可以将二者结合使用，算出好前缀的移动位数，再算出好后缀规则的移动位数取较大的作为真正的向后移动位数，能够保证更高效的匹配，如下
此时坏字符规则下移动 i - k = 5 - 3 = 2 位
好后缀规则没有匹配到，则直接向后移动模式字符串长度的位数 6 位，此时选择最大的 6 位进行移动
此时根据坏字符规则移动 i - k = 3 - 5 = -2 位
好后缀规则移动 4 位（与好后缀位置重合），此时选择最大的 4 位进行移动
这个列子举得不够好，没有出现坏字符移动位数 > 好后缀移动位数的情况，但是意思都懂如果出现了就向后移动坏字符匹配需要移动的位数就行
此时根据坏字符规则向后移动 i - k = 5 - 1 = 4 位，根据好后缀规则向后移动 2 位，取大的向后移动 4 位如下
后续的移动规则跟之前一样就不在赘述
时间复杂度讨论
相信大家根据上述的讲解后对 BM 算法的两种规则原理应该了解了，不过好像坏字符规则下，每次移动坏字符都要去模式串中遍历查找。
在好后缀中每次都要计算好后缀的后缀子串以及模式串的前缀子串然后对比，好像直观上性能也会有所影响，本文没有去详细推论 BM 的时间复杂度（因为确实比较复杂），但是在实现的思路上却有很可以优化的空间
算法实现及优化思路
在根据坏字符规则的匹配下，每次都需要将从模式串中遍历查找是否存在坏字符，这里可以将模式串的每个字符存入哈希表中比如存入 HashMap 中，从中查找的时候可以直接使用 map，O(1) 的时间复杂度来进行查询。
在根据好后缀字符规则的匹配下，可以提前将前缀子串的所有子串计算好，放入内存中，在好后缀匹配的时候如果好后缀串长度为 3，那么我们首先判断模式串中是否存在跟好后缀一样的串后，如果没有的话，就直接去之前缓存好的前缀子串中寻找长度 < 3 的前缀子串，找到了就向后移动对应的位置，没有找到就向后移动模式串长度的位数
参考
- 数据结构与算法之美