KMP算法python

KMP算法是一种高效的字符串匹配算法，它通过求出next()函数来实现匹配过程中的跳跃，避免了每次只滑动一个元素进行匹配的时间消耗。KMP算法的核心思想是利用模式串中已经匹配过的部分信息，来减少不必要的比较次数。

下面是KMP算法的Python代码示例：

def getNext(pattern):
    next = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
        while j > 0 and pattern[i] != pattern[j]:
            j = next[j-1]
        if pattern[i] == pattern[j]:
            j += 1
        next[i] = j
    return next

def KMP(text, pattern):
    next = getNext(pattern)
    i, j = 0, 0
    while i < len(text) and j < len(pattern):
        if text[i] == pattern[j]:
            i += 1
            j += 1
        else:
            if j > 0:
                j = next[j-1]
            else:
                i += 1
    if j == len(pattern):
        return True
    return False