引言

这几天碰到在主串中查找子串的问题，首先就是想到了直接暴力解，就是朴素的模式匹配算法，但是这种的时间复杂度太高了，于是三位大佬（D.E.Knuth，J.H.Morris和V.R.Pratt）就一起提出了一种新算法，人们称为KMP算法。
ps:大家可以先去看看这个up讲解的视频 最浅显易懂的 KMP 算法讲解
个人感觉讲解的很清晰

为什么KMP可以降低时间复杂度？

咱们先来看一个示例：
当我们使用朴素的模式匹配算法时：
1.

2.

3.

4.

5.

如上图过程，就是按照主串的每个索引分别开始和子串比较，直到完全匹配上
如果主串长度是m
子串长度是n
那么这个时间复杂度就是O(mn)
是不是有点高，接下来让我们来看看KMP算法

开始正文，KMP登场

我们再来举一个例子：

1.初始状态：

2.开始朴素的正常匹配：

3.发现可优化的部分：

我们可以发现，这时候当发现了不匹配的地方，如果按照原来的朴素匹配，我下一步应该这样：

但是按照例子来的话，既然子串所有字符都不相等，那么之前从[a-e]已经匹配成功，就没必要再从主串的第二位开始进行匹配了。
所以，优化的可能性就出现了，我们是否可以根据子串和主串的匹配情况，来使主串不要每次都重新回退很多位，而保持一直向前的状态？这样不就是线性的时间，并且省去了上面示例没必要的浪费情况。
再次回到上面的例子：
如果我们不采用朴素匹配的方式，那么可以怎么做呢？
我可以直接跳过前面已经匹配上的，从匹配失败的地方开始比较就可以。
为什么可以这么做？
首先，我们的子串每个字符串都不相同
所以我们匹配上的部分可以直接略过。就像下图这样：

那么这时候可能会出现一个问题，难道我们每次匹配失败都要把子串首位平移到与主串匹配失败的位置比较吗，这样不会出现问题吗？
当然会，就像下面这样：

但是正确情况确实这样：

问题出现了，为什么会这样？
因为子串中并不是所有的字符都是不一样的，两对（a,b）的出现使我们之前的暂时论断出现了错误。
但是我们发现的优化方法就要这么错过了吗？
不，这时候就需要我们的next数组了。
我们之前推断的情况是子串中没有任何重复的字符，那现在有重复的状态就不对了，而且根据以上实例验证我们应该跳过两位比较，而不是四位。
可以得出我们要是解决的子串中的重复问题，或许可以解决跳过比较的位数问题。
而next数组就是干这个的。
观察这个数组，如果数组里只有[a,b,c]那我们可以直接跳过两位，但是不巧，是[a,b,a],我们就只能跳到子串中a再次出现的位置了，就是说只能正常跳过一位比较，所以，我们就可以得出我们的next数组了，或者换句话说next数组是根据子串的最长相等前后缀得出来的。
什么是最长相等前后缀？
看下图：
前缀：

后缀：

所以我们可以得出最长相等前后缀的长度是1，前后缀是[a],也就是我们可以跳过的最长的，正确的长度。
我们可以把这个数值存储在next数组里面：得出对应的next数组为：

下面是计算next数组的代码实现：

#构造next数组
def build_next(patt):#参数是子串，也成为模式串
    next=[0]#初始第一个字符的最长相等前后缀是0
    prefix_len=0#当前共同前后缀的长度
    i=1#从第二个元素开始寻找相同的前后缀
    while i<len(patt):
        if patt[i]==patt[prefix_len]:
            prefix_len+=1
            next.append(prefix_len)
            i+=1
        else:
            if prefix_len==0:
                next.append(0)
                i+=1
            else:
                prefix_len=next[prefix_len-1]#有彩蛋
    return next

ps：这里有一点要记录，当出现没有匹配上，并且，前面已经出现了相等前后缀，且更新到prefix_len的情况时的处理办法：
也就是代码块的这个部分：

 prefix_len=next[prefix_len-1]

继续拿出我们这张图

前四位都可以正常理解，但是红框位置是怎么的出来的呢？
假设我们的c->a,是不是可以正常的最长前缀和+1，prefix_len更新为3
但是现在不行啊，那如果我们无法构造更长的，就只能向前看看，有没有更短的prefix_len能用了。
由于是最长前后缀相等，从前数prefix_len位 是等于 从后数prefix_len位，所以当prefix_len的情况不满足时，我们是不是可以看看**（prefix_len-1）**的情况满不满足？
欸，那不就是 prefix_len=next[prefix_len-1]

得到了next数组，就很好写KMP的查找代码啦

#进行kmp方式查找
def kmp_search(string,patt):
    next=build_next(patt)#构造next数组
    i,j=0,0#主串指针，子串指针
    while i<len(string):
        if string[i]==patt[j]:#如果主串和子串可以匹配上
            i+=1#那就同时向前继续找，和朴素模式匹配一样
            j+=1
        elif j>0:#如果没有匹配上，并且是两者之前部分匹配上了
            j=next[j-1]#可以根据next数组跳过子串的一些字符，获取前面已经匹配上的
        else:#子串的第一个字符就没匹配上，直接主串向前，子串不用动
            i+=1
        if j==len(patt):#全部匹配完成
        #如果不好看出来可以用两个完全相同的主串和子串进行验证
        #就能得出子串到底是在主串哪个位置开始查找到的，返回索引。
            return i-j

—完结撒花—
这次是记录一下KMP算法的学习过程，希望对大家有帮助，如果哪里有问题或者不足，请路过的朋友们帮忙指正一下~，感谢感谢！