背景

提起字符串匹配，可能很多人都會(huì)想到KMP算法 O(m+n)奖亚，但是其實(shí)KMP并不常用淳梦，因?yàn)橐廊皇锹模Ｓ玫钠鋵?shí)是BM算法 O(m/n)（Boyer-Moore算法）昔字，這就是很多文本編輯器的查找功能采用的算法谭跨，而Sunday算法是在其之上又做了一些改動(dòng)。下面我給大家簡(jiǎn)單介紹下Sunday算法與BM算法針對(duì)于KMP算法的差異點(diǎn)李滴。

思路

先說(shuō)下BM算法

首先的區(qū)別，與KMP從前往后掃描模式串不同蛮瞄，BM算法是從后往前對(duì)模式串進(jìn)行掃描與主串進(jìn)行匹配的

其核心就是兩個(gè)啟發(fā)策略：

（1）壞字符算法
當(dāng)出現(xiàn)一個(gè)壞字符時(shí), BM算法向右移動(dòng)模式串, 讓模式串中最靠右的對(duì)應(yīng)字符與壞字符相對(duì)所坯，然后繼續(xù)匹配。壞字符算法有兩種情況挂捅。

Case1：模式串中有對(duì)應(yīng)的壞字符時(shí)芹助，讓模式串中最靠右的對(duì)應(yīng)字符與壞字符相對(duì)（PS：BM不可能走回頭路，因?yàn)槿羰腔仡^路，則移動(dòng)距離就是負(fù)數(shù)了状土，肯定不是最大移動(dòng)步數(shù)了）无蜂，如下圖。

Case1

Case2：模式串中不存在壞字符蒙谓，那么直接右移整個(gè)模式串長(zhǎng)度這么大步數(shù)斥季，如下圖。

Case2

（2）好后綴算法
如果程序匹配了一個(gè)好后綴, 并且在模式串中還有另外一個(gè)相同的后綴（參見case1）或后綴的部分（參見case2）, 那把下一個(gè)后綴或部分移動(dòng)到當(dāng)前后綴位置累驮。即酣倾，模式串的后u個(gè)字符和主串都已經(jīng)匹配了，但是接下來(lái)的一個(gè)字符不匹配谤专，如果說(shuō)后u個(gè)字符在模式串其他位置也出現(xiàn)過(guò)或部分出現(xiàn)躁锡，我們將模式串右移到前面的u個(gè)字符（參見case1）或部分和最后的u個(gè)字符或部分相同（參見case2）的位置，如果說(shuō)后u個(gè)字符在模式串其他位置完全沒(méi)有出現(xiàn)置侍，那么就直接右移整個(gè)模式串（參見case3）映之，如下圖所示：

Case1：模式串中有子串和好后綴完全匹配，則將最靠右的那個(gè)子串移動(dòng)到好后綴的位置繼續(xù)進(jìn)行匹配蜡坊。

Case1

Case2：如果不存在和好后綴完全匹配的子串杠输，則在好后綴中找到具有如下特征的最長(zhǎng)子串,使得P[m-s…m]=P[0…s]。

Case2

Case3：如果完全不存在和好后綴匹配的子串算色，則右移整個(gè)模式串抬伺。

（3）移動(dòng)規(guī)則
BM算法的移動(dòng)規(guī)則是：
BM算法是每次向右移動(dòng)模式串的距離是 MAX（shift（好后綴），shift（壞字符））灾梦，即按照好后綴算法和壞字符算法計(jì)算得到的最大值峡钓。

缺點(diǎn)

BM算法與KMP思想類似，但是更好了利用了預(yù)處理數(shù)組若河，使得更有效率能岩，但是模式串的預(yù)處理數(shù)組也變得相對(duì)更加復(fù)雜，所以當(dāng)面臨較小場(chǎng)景時(shí)萧福，并不一定適合選用BM算法拉鹃。

優(yōu)點(diǎn)

• 時(shí)間復(fù)雜度

KMP O(m+n)
BM O(m/n) - O(m*n)

• 思維優(yōu)勢(shì)
  BM算法從后往前掃描模式串使得它更好的利用了“后綴”，BM算法的啟發(fā)策略也使得模式串可以更加有效率的移動(dòng)鲫忍，在面臨實(shí)際使用中的較大匹配場(chǎng)景時(shí)膏燕，效率提高明顯。

BM算法的具體實(shí)現(xiàn)悟民，例如好后綴算法和壞字符算法 模式串的預(yù)處理數(shù)組如何實(shí)現(xiàn)坝辫？
請(qǐng)移步某前輩的文章： grep之字符串搜索算法Boyer-Moore由淺入深，這里不細(xì)說(shuō)了射亏，只介紹下核心差異點(diǎn)近忙。

知道了BM算法竭业，下面我們來(lái)說(shuō)Sunday算法

Sunday算法

Sunday算法是從前往后掃描模式串的，其思路更像是對(duì)于“壞字符”策略的升華及舍。關(guān)注的是主串中參與匹配的最末字符（并非正在匹配的）的下一位未辆，稍后看圖更容易理解

Sunday算法只有一個(gè)啟發(fā)策略

Case1：當(dāng)遇到不匹配的字符時(shí)，如果關(guān)注的字符沒(méi)有在模式串中出現(xiàn)則直接跳過(guò)
即移動(dòng)位數(shù) = 子串長(zhǎng)度 + 1锯玛；

Case1

Case2： 當(dāng)遇到不匹配的字符時(shí)咐柜，如果關(guān)注的字符在模式串中也存在時(shí)，其
移動(dòng)位數(shù) = 模式串長(zhǎng)度 - 該字符最右出現(xiàn)的位置(以0開始)
或者移動(dòng)位數(shù) = 模式串中該字符最右出現(xiàn)的位置到尾部的距離 + 1
看下例子：

Case2

策略是很清晰簡(jiǎn)單的更振，但是想一下就可以發(fā)現(xiàn)炕桨，這個(gè)算法缺點(diǎn)也很明顯：

缺點(diǎn)

如果是下面這個(gè)情況，會(huì)怎么樣肯腕？
主串：baaaabaaaabaaaabaaaa
子串：aaaaa
沒(méi)錯(cuò)献宫，這個(gè)時(shí)候，效率瞬間變成了O(m*n)
Sunday算法的移動(dòng)是取決于子串的实撒，這一點(diǎn)跟BM算法沒(méi)什么區(qū)別姊途，當(dāng)這個(gè)子串重復(fù)很多的時(shí)候，就會(huì)非常糟糕了知态。大家知道這一點(diǎn)捷兰，有所取舍就好

優(yōu)點(diǎn)

• 時(shí)間復(fù)雜度

KMP O(m+n)
BM O(m/n) - O(m*n)
Sunday O(m/n) - O(m*n)
實(shí)際使用中 Sunday算法比BM算法略優(yōu)

• 思維優(yōu)勢(shì)
  我理解Sunday算法優(yōu)在，它的思路很簡(jiǎn)單负敏，很清晰贡茅，而現(xiàn)實(shí)生活的實(shí)際場(chǎng)景中，又恰恰能較好的規(guī)避它的缺點(diǎn)其做，使得它能夠大大增加匹配效率顶考。

代碼

• 實(shí)例：LeetCode.28 - 實(shí)現(xiàn)strStr()

def sunday_search(self, haystack: str, needle: str) -> int:
        if not needle:
            return 0

        offset = {}
        n_l = len(needle)

        for i in range(n_l):
            offset[needle[i]] = n_l - i

        i, j, h_l = 0, 0, len(haystack)

        while i <= h_l - n_l:
            j = 0

            while haystack[i + j] == needle[j]:
                j += 1
                if j == n_l:
                    return i

            if i + n_l == h_l:
                return -1

            if haystack[i + n_l] in offset:
                i += offset[haystack[i + n_l]]
            else:
                i += n_l + 1

        return -1

以上，歡迎大家討論妖泄，共同進(jìn)步

歡迎大家關(guān)注我的公眾號(hào)

半畝房頂