背景

提起字符串匹配，可能很多人都会想到KMP算法 O(m+n)，但是其实 KMP 并不常用，因为依然是慢的，常用的其实是BM算法 O(m/n)（Boyer-Moore 算法），这就是很多文本编辑器的查找功能采用的算法，而Sunday算法是在其之上又做了一些改动。

思路

先说下 BM 算法

其核心就是两个启发策略：

（1）坏字符算法策略

当出现一个坏字符时, BM 算法向右移动模式串, 让模式串中最靠右的对应字符与坏字符相对，然后继续匹配。坏字符算法有两种情况。

Case1：模式串中有对应的坏字符时，让模式串中最靠右的对应字符与坏字符相对（PS：BM 不可能走回头路，因为若是回头路，则移动距离就是负数了，肯定不是最大移动步数了），如下图。

case1

Case2：模式串中不存在坏字符，很好，直接右移整个模式串长度这么大步数，如下图。

case2

（2）好后缀算法策略

如果程序匹配了一个好后缀, 并且在模式中还有另外一个相同的后缀或后缀的部分, 那把下一个后缀或部分移动到当前后缀位置。假如说，pattern 的后 u 个字符和 text 都已经匹配了，但是接下来的一个字符不匹配，我需要移动才能匹配。如果说后 u 个字符在 pattern 其他位置也出现过或部分出现，我们将 pattern 右移到前面的 u 个字符或部分和最后的 u 个字符或部分相同，如果说后 u 个字符在 pattern 其他位置完全没有出现，很好，直接右移整个 pattern。这样，好后缀算法有三种情况，如下图所示：

Case1：模式串中有子串和好后缀完全匹配，则将最靠右的那个子串移动到好后缀的位置继续进行匹配。

case1

Case2：如果不存在和好后缀完全匹配的子串，则在好后缀中找到具有如下特征的最长子串,使得 P[m-s…m]=P[0…s]。

case2

Case3：如果完全不存在和好后缀匹配的子串，则右移整个模式串。

（3）子串移动规则

BM 算法的移动规则是：

偏移量为 MAX（shift（好后缀），shift（坏字符）），即

BM 算法是每次向右移动模式串的距离是，按照好后缀算法和坏字符算法计算得到的最大值。

shift（好后缀）和 shift（坏字符）通过模式串的预处理数组的简单计算得到

而这两个策略的具体实现，这里不再多说，请移步前辈的文章观看：

grep之字符串搜索算法Boyer-Moore由浅入深

知道了 BM 算法，下面我们来说 Sunday 算法

Sunday 算法

Sunday 算法是从前往后匹配（BM 是从后往前），关注的是主串中`参与匹配的最末字符（并非正在匹配、或者说参与比较的）的下一位`，好好记住这句话，因为这里是 Sunday 算法里最不容易理解的地方了，对，最不容易，而且还是个单纯的文字理解

Sunday 算法只有一个启发策略

Case1：如果关注的字符没有在子串中出现则直接跳过

即移动位数 = 子串长度 + 1；

case1

Case2： 否则，其

移动位数 = 子串长度 - 该字符最右出现的位置(以0开始)

或者移动位数 = 子串中该字符最右出现的位置到尾部的距离 + 1

case2

简直简单的不像话，但是其实简单想一下就知道，这个算法缺点也很明显，有得有失嘛，这个是必然的

缺点

如果是下面这个情况，会怎么样？

主串：baaaabaaaabaaaabaaaa

子串：aaaaa

没错，这个时候，效率瞬间变成了O(m*n)

Sunday 算法的移动是取决于子串的，这一点跟 BM 算法没什么区别，当这个子串重复很多的时候，就会非常糟糕了。大家知道这一点，有所取舍就好

优点

##### 优点

* 时间复杂度

```

KMP O(m+n)

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

Sunday O(m/n) - O(m*n)

```

* 思维优势

我理解 BM 算法和 Sunday 算法的思路优在，其视角不再是字符，而是词。尤其是 BM 的“好后缀”策略，很明显的展示了这种感觉，词与词之间的后缀共用，是常有的事，此时，这个“好后缀”是应该作为一个整体元素参与匹配。

代码

• 实例：LeetCode.28 - 实现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

以上，欢迎大家讨论，共同进步

欢迎大家关注我的公众号，一起探讨技术