1 暴力破解法
在主串A中查找模式串B的出现位置，其中如果A的长度是n，B的长度是m，则n > m。当我们暴力匹配时，在主串A中匹配起始位置分别是 0、1、2….n-m 且长度为 m 的 n-m+1 个子串。
对应代码是：
3.3 好后缀规则
好后缀跟坏后缀道理类似，从后往前匹配，直到遇到不匹配的字符x，那主串x之前的就叫好后缀。
此时移动的规则如下：
3.4.2 正式代码
有了suffix跟prefix数组后，看下移动规则。假设好后缀串长度=k，如果k != 0，说明有好后缀，接下来通过suffix[k]的值来判断如何移动。
suffix[k] != -1，不等于时说明匹配上了，模式串后移 j-suffix[k]+1 位，其中 j 表示坏字符对应的模式串中的字符下标。
suffix[k] = -1，等于时说明好后缀没匹配上，那就看下子串的匹配情况，好后缀的后缀子串长度是 b[r, m-1]，其中 r = [j+2,m-1]，后缀子串长度 k=m-r，如果 prefix[k] = true，说明长度为 k 的后缀子串有可匹配的前缀子串，这样我们可以把模式串后移 r 位。
如果都没匹配上，那就直接将模式串后移m位。
3.5 复杂度分析
整个BM算法用到了额外的 sl、suffix、prefix三个数组，其中sl数组大小跟字符集大小有关，suffix 数组和 prefix 数组的大小跟模式串长度 m 有关。如果处理字符集很大的字符串匹配问题，bc 数组对内存的消耗就会比较多。
因为好后缀和坏字符规则是独立的，如果我们运行的环境对内存要求苛刻，可以只使用好后缀规则，不使用坏字符规则，这样就可以避免 bc 数组过多的内存消耗。不过，单纯使用好后缀规则的 BM 算法效率就会下降一些了。
BM 算法的时间复杂度分析起来是非常复杂，一般在3n~5n之间。
4 KMP 算法
KMP算法跟BM算法类似，从前往后匹配，把能匹配上的叫好前缀，不能匹配上的叫坏字符。
遇到坏字符后就要进行主串好前缀后缀子串跟模式串的前缀子串进行对比，问题是对于已经比对过的好前缀，能否找到一种规律，将模式串一次性滑动很多位？
思路是将主串中好前缀的后缀子串和模式串中好前缀的前缀子串进行对比，获取模式串中最大可以匹配的前缀子串。一般把好前缀的所有后缀子串中，最长的可匹配前缀子串的那个后缀子串，叫作最长可匹配后缀子串。对应的前缀子串，叫作最长可匹配前缀子串。假如现在最长可匹配后缀子串 = u，最长可匹配前缀子串 = v，获得u跟v的长度为k，此时在主串中坏字符位置为i，模式串中为j，接下来将模式串后移j-k位，然后将待比较的模式串位置j = j-k进行比较。
4.1 Next 数组存在意义
那最长可匹配前缀跟后缀我们用模式串就可以求解了。仿照BM算法，预先计算好就行。在KMP算法中提前构造个next数组。其中next数组的下标用来存储前缀子串最后一个数据的index，对应的value保存的是这个字符串的后缀子串集合跟前缀子串集合的交集。
干说可能不太好理解，我们以"abababca"为例。它的部分匹配表(Partial Match Table)数组如下：
接下来对value值的获取进行解释，如果字符串A和B，存在A=BS，其中S是任意的非空字符串，那就称B为A的前缀。例如”what”的前缀包括{"w","wh","wha"}，我们把所有前缀组成的 字符串的前缀集合。同样可以定义后缀A=SB， 其中S是任意的非空字符串，那就称B为A的后缀，例如"Potter"的后缀包括{"otter", "tter", "ter", "er", "r"}，然后把所有后缀组成字符串的后缀集合。要注意 字符串本身并不是自己的后缀。
PMT数组中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。例如，对于"aba"，它的前缀集合为{"a", "ab"}，后缀集合为{"ba", "a"}。两个集合的交集为{"a"}，那么长度最长的元素就是字符串"a"了，长度为1，所以"aba"的Next数组value = 1，同理对于"ababa"，它的前缀集合为{"a", "ab", "aba", "abab"}，它的后缀集合为{"baba", "aba", "ba", "a"}， 两个集合的交集为{"a", "aba"}，其中最长的元素为"aba"，长度为3。
我们以主串"ababababca"中查找模式串"abababca"为例，如果在j处字符不匹配了，那在模式串[0,j-1]的数据串"ababab"中，前缀集合跟后缀集合的交集最大值就是长度为4的"abab"。
基于此就可以使用PMT加速字符串的查找了。我们看到如果是在
j位失配，那么影响 j 指针回溯的位置的其实是第 j−1 位的 PMT 值，但是编程中为了方便一般不直接使用PMT数组而是使用Next数组，Next数组的value其实就是存储的这个前缀的最长可以匹配前缀子串的结尾字符下标，其中如果匹配不到用-1代替。 4.2 KMP 匹配代码
至此你会发现只要搞明白了PMT存在的意义，然后顺着思路推Next数组即可。
4.3 Next 数组求解
当要计算next[i]时，前面计算过的next[0~i-1]是否可以被用来快速推导出next[i]呢？
情况一：如果next[i-1] = k-1，那此时b[0,i-1]的最长可匹配前缀子串是b[0,k-1]，如果b[0,i-1]的下个字符b[i]跟b[0,k-1]的下个字符b[k]相等，那next[i] = k。
情况二：假设b[0,i]最长可用后缀子串是b[r,i]，那b[r,i-1]肯定是b[0,i-1]的可匹配后缀子串，但不一定是最长可匹配后缀子串。比如字符串b = "dexdecdexdex"，此时最长可匹配后缀子串是"dex"，b去掉最后的'x'成为B，此时虽然"de"是B的可匹配后缀子串，但"dexde"才是最长后缀子串！也就是说b[0, i-1]最长可匹配后缀子串对应的模式串的前缀子串的下一个字符并不等于 b[i]。
KMP空间复杂度：该算法只需要一个额外的 next 数组，数组的大小跟模式串相同。所以空间复杂度是 O(m)，m 表示模式串的长度。
KMP时间复杂度：next 数组计算的时间复杂度是 O(m) + 匹配时候时间复杂度是 O(n) = O(m+n)
5 参考
极客时间KMP：https://time.geekbang.org/column/article/71845
知乎KMP：https://www.zhihu.com/question/21923021
袁厨KMP：https://t.1yb.co/i95V
本文分享自微信公众号 - sowhat1412（sowhat9094）。
如有侵权，请联系 [email protected] 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。