kmp算法改进python

KMP算法是一种字符串匹配算法，用于在一个主串中查找一个模式串的出现位置。它通过利用已经匹配过的部分信息，避免不必要的比较，从而提高了匹配的效率。

下面是KMP算法的改进版本的Python代码示例：

def getNext(p):
    n = len(p)
    next = [0] * n
    next[0] = -1
    i, j = 0, -1
    while i < n - 1:
        if j == -1 or p[i] == p[j]:
            i += 1
            j += 1
            if p[i] != p[j]:
                next[i] = j
            else:
                next[i] = next[j]
        else:
            j = next[j]
    return next

def kmp(t, p):
    m, n = len(t), len(p)
    i, j = 0, 0
    next = getNext(p)
    while i < m and j < n:
        if j == -1 or t[i] == p[j]:
            i += 1
            j += 1
        else:
            j = next[j]
    if j == n:
        return i - j
    else:
        return -1

t = "ABABDABACDABABCABAB"
p = "ABABCABAB"
index = kmp(t, p)
print("Pattern found at index:", index) # 输出：Pattern found at index: 10

这段代码中，`getNext`函数用于计算模式串的`next`数组，`kmp`函数用于在主串中查找模式串的位置。通过使用`next`数组，KMP算法能够在匹配失败时，跳过一些已经匹配过的字符，从而提高匹配的效率。