我们想象一根指针指向了B数组当中接下来要匹配的位置，如果匹配失败了，它就会跳转到Next数组当中记录的位置去，匹配成功了我们就向后移动一位。在有了Next数组之后，我们写出代码来真的很容易了：
def kmp(var_str, template_str): # var_str即A串 # template_str模式串即B串 # 我们在两个字符串前加上了占位符 var_str = '$' + var_str template_str = '$' + template_str next = generate_next(template_str) n, m = len(var_str), len(template_str) # head指向要匹配的位置的前一位 head = 0 for i in range(1, n): # 由于next数组很长，可能失败多次 # 直到head+1的位置能匹配上或者head等于0 while head > 0 and template_str[head+1] != var_str[i]: head = next[head] # 匹配上了则head变长一位 if template_str[head+1] == var_str[i]: head += 1 # 如果head长度等于B串了，则表示匹配成功 if head == m - 1: return True return False对于A串中的每一个位置来说，我们都在B串当中遍历了每一个有可能构成匹配的前缀。所以说这个算法是可行的，一定可以获得解。另外一个问题是复杂度的问题，为什么我们用了两重循环，但仍然是\(O(n)\)的算法呢？
其实很简单，因为while循环只会让head减小，而不会让head增加。head增加是在for循环里执行的，也就是说head最多增加n次。那么对应的while循环也就最多执行n次，因为head是非负的。所以while循环在整个for循环执行的过程当中最多执行了n次，整体执行的次数仍然是\(O(n)\)级别的而不是\(n^2\)级，当然是线性的算法。
求解Next
到这里，问题只剩下了一个，就是这个Next怎么来呢？
其实我们在之前讲Next数组的使用的时候已经泄露天机了，我们再来看下上图，不知道大家能感觉到什么。
后面一个A的Next值是1，也就是第一个A的下标，后面一个B的Next值是2，也就是第一个B的下标。换句话说第二个A能够和位置1的A匹配，后面的AB能和前缀的AB匹配。也就是说Next数组其实就是B数组自己和自己匹配的结果，我们在一开始的时候将整个Next数组全部置为0，然后依次递推迭代出所有的Next的值。
我们在求解Next[i]的时候我们可以利用上Next[i-1]的值，因为Next[i-1]存储的是能够与B[i-1]匹配的前缀的结尾位置。如果B[Next[i-1]+1]等于B[i]，那么说明Next[i] = Next[i-1] + 1。如果不等的话，我们可以用while循环来寻找能够匹配上的前缀。也就是说这是一个递推的过程，不过要注意一点我们计算Next数组要从2开始，因为对于1来说，Next[1]一定等于0。
def generate_next(var_str): n = len(var_str) next = [0 for _ in range(n)] for i in range(2, n): # 用next[i-1]作为开始寻找能够匹配上的最长next[i] head = next[i-1] while head > 0 and var_str[head+1] != var_str[i]: head = next[head] # 如果匹配上了，head+1 if var_str[head+1] == var_str[i]: head = head + 1 # 记录下来 next[i] = head return next总结
到这里，我们关于KMP算法的介绍就结束了，不知道大家看完之后感受如何，是不是有点蒙圈呢？
其实蒙圈是正常的，我第一次学的时候足足看了好几遍才算是看明白。这毕竟是一个比较巧妙的算法，想要通过阅读一篇文章就完全学会还是比较困难的，最好的还是亲自动手实现一下试试。KMP算法我最大的感受就是如果你把整个算法的逻辑都串起来了，那么即是自己从头到尾推导一遍难度也不是很大（我就在面试当中推导过一次）。如果你没能把逻辑串起来，那么觉得难理解看不懂是正常的，你可能需要再读一遍或者是寻找一些其他的资料查漏补缺。
今天的文章到这里就结束了，如果喜欢本文的话，请来一波素质三连，给我一点支持吧（关注、转发、点赞）。