背景
提起字符串匹配，可能很多人都会想到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算法的移动规则是：
将3中算法基本框架中的j += BM()，换成j += MAX（shift（好后缀），shift（坏字符）），即
BM算法是每次向右移动模式串的距离是，按照好后缀算法和坏字符算法计算得到的最大值。
shift（好后缀）和shift（坏字符）通过模式串的预处理数组的简单计算得到。坏字符算法的预处理数组是bmBc[]，好后缀算法的预处理数组是bmGs[]。
而这两个算法的具体实现，这里不再说，请移步前辈的文章观看： grep之字符串搜索算法Boyer-Moore由浅入深
知道了BM算法，下面我们来说Sunday算法
Sunday算法
Sunday算法是从前往后匹配（BM是从后往前），关注的是主串中参与匹配的最末字符（并非正在匹配、或者说参与比较的）的下一位，好好记住这句话，因为这里是Sunday算法里最不容易理解的地方了，对，最不容易，而且还是个单纯的文字理解
Sunday算法只有一个启发策略
Case1：如果关注的字符没有在子串中出现则直接跳过
即移动位数 = 子串长度 + 1；
Case2： 否则，其
移动位数 = 子串长度 - 该字符最右出现的位置(以0开始)
或者移动位数 = 子串中该字符最右出现的位置到尾部的距离 + 1
看下例子：
Case1
Case2
简直简单的不像话，但是其实简单想一下就知道，这个算法缺点也很明显，有得有失嘛，这个是必然的
缺点
如果是下面这个情况，会怎么样？
主串：baaaabaaaabaaaabaaaa
子串：aaaaa
没错，这个时候，效率瞬间变成了O(m*n)
Sunday算法的移动是取决于子串的，这一点跟BM算法没什么区别，当这个子串重复很多的时候，就会非常糟糕了
大家知道这一点，然后有所取舍，就好啦，下面上代码吧
代码
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
以上，欢迎大家讨论，共同进步
欢迎大家关注我的公众号
半亩房顶
网友评论