python的KMP算法

KMP算法是一种字符串匹配算法，用于在一个文本串S内查找一个模式串P的出现位置。它的时间复杂度为O(m+n)，其中m和n分别为文本串S和模式串P的长度。KMP算法的核心思想是利用已经匹配过的信息，尽量减少模式串与文本串的匹配次数。

具体来说，KMP算法通过预处理模式串P，得到一个next数组，其中next[i]表示当P[i]与S[j]不匹配时，下一次应该从哪个位置开始匹配。这个next数组可以在O(m)的时间内预处理出来。然后，我们从文本串S的第一个字符开始，依次与模式串P进行匹配。如果当前字符匹配成功，则继续匹配下一个字符；则，根据next数组的值，将模式串P向右移动一定的距离，然后继续匹配。