BM算法简介

BM是字符串搜索算法。

字符串搜索单模式下有BF、RK、BM、KMP算法，其中BF是暴力搜索，RK是利用hash的一种算法，BM和KMP是最常用的字符串匹配算法，假定模式串长度为m，文本长度是n，则BM最大算法复杂度在O(3n)，KMP算法复杂度在O(m+n)。

学习姿势

BM算法恐怕我们一般都不会去写，为何要去学习这种算法呢？算法能训练人的逻辑能力，当然要学。但是以什么样的姿势来学这种算法呢，平心而论，这种算法学习复杂度算是比较高的，怎样去学习比较合适呢？

就我个人的体会来说，按照算法思想和算法实现的套路来学习能显著的降低学习复杂度。怎么理解这个套路呢？

• 算法思想属于高层一点的抽象，这里的算法思想结合上算法主流程来理解，互相印证，算法的主流程也算是算法思想这个层面
• 算法实现，算法主流程已经放在算法思想中了，那么算法实现指什么呢？看过《编程珠玑》，第二部分强调的就是算法写好以后的优化，没错，这里指的就是优化。对于这部分，如果能理解就理解，理解不了就当训练自己的算法思维了。

一旦以这种方式去理解这两个算法，就会发现学习曲线降低了很多。

BM算法

BM = (坏字符规则 + 好后缀规则） （算法思想） + （坏字符hash数组实现 + 好后缀巧算）（优化）

BM的算法思想

BM算法与两条规则有关，理解了这两条规则就理解了BM的算法思想。BM文本串和模式串是 从后向前 比较（特别注意一下这点）。

坏字符规则

- c是坏字符

第一个不匹配的就是坏字符，如图就是文本串的c。不考虑好后缀的情况下，你会怎么办，就是直接把模式串移动到坏字符的后面。

• 移动到坏字符后面

如果说坏字符在模式串种存在， 直接移动到后面，可能移动过头了。例如说如下情形，直接移动到坏字符c后面就过头了。

• 移动过头了
  

  这时就需要结合好后缀来匹配。

好后缀规则

好后缀有两种情况

• 情形一 好后缀在模式串种可以找到
  从后向前匹配，在遇到坏字符之前，这些匹配的串就是好后缀，如下橙色的ab就是好后缀。
• 好后缀

好后缀可以在模式串种找到，直接就移动到模式串种的匹配处。

• image.png

• 情形二 好后缀在模式串种可以找不到

• image.png
  

  这种情况下找不到，应该怎么移动呢，就要找好后缀的后缀子串和模式串的前缀子串的最大匹配串

• image.png
  

  如图，找到ab的后缀子串和bb的前缀子串最长匹配串时b，因此移动到b的位置。

算法思想讲完了，就是这样的，再配合上主算法代码就完成了算思想的学习

class Solution:
    def search(self, inputStr, pattern):
        if len(inputStr) < len(pattern):
            return -1
        bc = self.generateBC(pattern)
        suffix, prefix = self.generateGoodSuffix(pattern)

        i = 0
        patternLength = len(pattern)
        while i <= len(inputStr) - patternLength:
            j = patternLength - 1
            while j >= 0:
                if inputStr[i+j] != pattern[j]:
                    break
                j -= 1
            if j < 0: # match
                return i
            # exist bad chracter, i + bad c
            x = j - bc[ord(inputStr[i + j]) - ord('a')]
            #exist good suffix
            y = 0
            if j < patternLength - 1:
                y = moveByGoodSuffix(j, patternLength, suffix, prefix)
            i = i + max(x, y)
        return -1

    def moveByGoodSuffix(j, length, suffix, prefix):
        k = length - 1 - j # length of good suffix
        if suffix[k] != -1:
            return j - suffix[k] + 1
        r = j + 2
        while r < length - 1:
            if prefix[length - r + 1]:
                return r
        return j + 1

BM的算法实现（优化）

对于坏字符位置以及好后缀的位置的计算属于优化部分，就不直接多说了，上代码

• 坏字符优化

    def generateBC(self, m):
        bc = [-1] * 26
        for i in range(len(m)):
            bc[ord(m[i]) - ord('a')] = i        
        return bc
···
这里直接利用hash数组，以空间换时间。比较容易理解，就不再赘述了。

- 好后缀计算

def generateGoodSuffix(self, m):
    length = len(m)
    suffix = [-1] * length
    prefix = [False] * length
    for i in range(length - 1):
        j = i
        k = 0
        while j>=0 and m[j] == m[length - 1 - k]:
            j -= 1
            k += 1
        if k: suffix[k] = j + 1
        if j == -1: prefix[k] = True
    return (suffix, prefix)

这个计算是个难点，但也不再赘述了，可以到网上查一下。关键想说的就是，按照算法原理和实现的套路分开理解后，对于实现，可以不再往下，学习到第一步算法原理就行了。算法实现就是优化中的预先计算存储的优化思路。

小结

按照算法原理和算法实现（优化）的套路，可以降低学习的复杂度，对于字符串搜索的KMP算法，也可以用同样的套路来进行学习。KMP算法的算法实现（优化）可以说是非常难以理解的，是一种动态规划的算法，但是如果抓住这个套路，即使理解不了算法实现（优化），我们理解了算法思想也是可以的。