BM算法簡介

BM是字符串搜索算法聋呢。

字符串搜索單模式下有BF苗踪、RK、BM削锰、KMP算法通铲，其中BF是暴力搜索，RK是利用hash的一種算法器贩，BM和KMP是最常用的字符串匹配算法颅夺，假定模式串長度為m，文本長度是n磨澡，則BM最大算法復(fù)雜度在O(3n)碗啄，KMP算法復(fù)雜度在O(m+n)。

學(xué)習(xí)姿勢

BM算法恐怕我們一般都不會去寫稳摄，為何要去學(xué)習(xí)這種算法呢稚字？算法能訓(xùn)練人的邏輯能力，當(dāng)然要學(xué)厦酬。但是以什么樣的姿勢來學(xué)這種算法呢胆描，平心而論，這種算法學(xué)習(xí)復(fù)雜度算是比較高的仗阅，怎樣去學(xué)習(xí)比較合適呢昌讲？

就我個人的體會來說，按照算法思想和算法實現(xiàn)的套路來學(xué)習(xí)能顯著的降低學(xué)習(xí)復(fù)雜度减噪。怎么理解這個套路呢短绸？

算法思想屬于高層一點的抽象，這里的算法思想結(jié)合上算法主流程來理解筹裕，互相印證醋闭，算法的主流程也算是算法思想這個層面
算法實現(xiàn)，算法主流程已經(jīng)放在算法思想中了朝卒，那么算法實現(xiàn)指什么呢证逻？看過《編程珠璣》，第二部分強調(diào)的就是算法寫好以后的優(yōu)化抗斤，沒錯囚企，這里指的就是優(yōu)化。對于這部分瑞眼，如果能理解就理解龙宏，理解不了就當(dāng)訓(xùn)練自己的算法思維了。

一旦以這種方式去理解這兩個算法伤疙，就會發(fā)現(xiàn)學(xué)習(xí)曲線降低了很多烦衣。

BM算法

BM = (壞字符規(guī)則 + 好后綴規(guī)則）（算法思想） + （壞字符hash數(shù)組實現(xiàn) + 好后綴巧算）（優(yōu)化）

BM的算法思想

BM算法與兩條規(guī)則有關(guān)，理解了這兩條規(guī)則就理解了BM的算法思想。BM文本串和模式串是從后向前比較（特別注意一下這點）花吟。

壞字符規(guī)則

c是壞字符

第一個不匹配的就是壞字符，如圖就是文本串的c厨姚。不考慮好后綴的情況下衅澈，你會怎么辦，就是直接把模式串移動到壞字符的后面谬墙。

移動到壞字符后面

如果說壞字符在模式串種存在今布，直接移動到后面，可能移動過頭了拭抬。例如說如下情形部默，直接移動到壞字符c后面就過頭了。

移動過頭了

這時就需要結(jié)合好后綴來匹配造虎。

好后綴規(guī)則

好后綴有兩種情況

情形一好后綴在模式串種可以找到
從后向前匹配傅蹂，在遇到壞字符之前，這些匹配的串就是好后綴算凿，如下橙色的ab就是好后綴份蝴。
好后綴

好后綴可以在模式串種找到，直接就移動到模式串種的匹配處氓轰。

image.png
情形二好后綴在模式串種可以找不到
image.png

這種情況下找不到婚夫，應(yīng)該怎么移動呢，就要找好后綴的后綴子串和模式串的前綴子串的最大匹配串
image.png

如圖署鸡，找到ab的后綴子串和bb的前綴子串最長匹配串時b案糙，因此移動到b的位置。

算法思想講完了靴庆，就是這樣的时捌，再配合上主算法代碼就完成了算思想的學(xué)習(xí)

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的算法實現(xiàn)（優(yōu)化）

對于壞字符位置以及好后綴的位置的計算屬于優(yōu)化部分，就不直接多說了撒穷，上代碼

壞字符優(yōu)化

    def generateBC(self, m):
        bc = [-1] * 26
        for i in range(len(m)):
            bc[ord(m[i]) - ord('a')] = i        
        return bc
···
這里直接利用hash數(shù)組匣椰，以空間換時間。比較容易理解端礼，就不再贅述了禽笑。

- 好后綴計算

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)

這個計算是個難點，但也不再贅述了蛤奥，可以到網(wǎng)上查一下佳镜。關(guān)鍵想說的就是，按照算法原理和實現(xiàn)的套路分開理解后凡桥，對于實現(xiàn)蟀伸，可以不再往下，學(xué)習(xí)到第一步算法原理就行了。算法實現(xiàn)就是優(yōu)化中的預(yù)先計算存儲的優(yōu)化思路啊掏。

小結(jié)

按照算法原理和算法實現(xiàn)（優(yōu)化）的套路蠢络，可以降低學(xué)習(xí)的復(fù)雜度，對于字符串搜索的KMP算法迟蜜，也可以用同樣的套路來進(jìn)行學(xué)習(xí)刹孔。KMP算法的算法實現(xiàn)（優(yōu)化）可以說是非常難以理解的，是一種動態(tài)規(guī)劃的算法娜睛，但是如果抓住這個套路髓霞，即使理解不了算法實現(xiàn)（優(yōu)化），我們理解了算法思想也是可以的畦戒。

學(xué)習(xí)BM算法的姿勢