Python | KMP算法的实现

引言

每一本《数据结构》方面的书应该都会讲KMP算法，KMP算法可以说是知名度非常高的算法之一，为什么会叫做KMP算法？是因为KMP是由三位大牛：D.E.Knuth、J.H.Morris和V.R.Pratt几乎同时发现的。所以取了每个人的第一个字母叫做KMP算法。

问题描述

给你一个母串和一个子串；请在母串中寻找子串如果母串中存在子串则返回True，不存在则返回False。

示例：母串：ababababcabc，子串：abababca

输入：ababababcabc

abababca

输出：True

解决方案

如KMP算法的时间复杂度为O（m+n）比暴力破解的时间复杂度O（m*n）小很多，这是因为在KMP算法中子串和母串不匹配的时候不会将子串向右挪移1位，而是将子串向后挪移k位。

如何确定子串向后挪移的位数呢？这个就像需要建立next数组来进行匹配，next数组就是子串中每一个位置的最大公共长度。最大公共长度在算法导论里面就被记为next数组。

计算next数组就是计算子串中每一个位置的最大公共长度。简单来说可以理解为遮住这个元素，去查看这个元素前面的相同前缀和后缀的长度，这个长度就是该元素对应的值，如图。

确定next数组后我们就可以开始子串与母串的匹配，当匹配到的元素值不同时，查找子串中该元素对应的next值，根据next值来确定子串该如何移动，移动后再开始新一次的匹配，一直循环这个过程直到匹配结束。

结语

KMP算法的核心就是在于next数组的建立，建立正确的next数组至关重要，通过next数组里面的next值可以帮助我们有效的减少循环次数和节约大量的时间。