KMP算法 python

KMP算法是一种字符串匹配算法，可以在O(n+m)的时间复杂度内查找一个字符串中是否包含另一个字符串。以下是KMP算法的Python实现：

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

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

其中，`kmp`函数用于查找字符串，`get_next`函数用于生成模式串的next数组。在`kmp`函数中，`i`指向原字符串中正在匹配的位置，`j`指向模式串中正在匹配的位置。如果当前字符匹配成功，则`i`和`j`同时向右移动一位；如果当前字符匹配失败，则通过next数组将`j`移动到下一个匹配位置。当`j`移动到模式串的末尾时，表示匹配成功，返回在原字符串中匹配成功的位置；否则，匹配失败，返回-1。

在`get_next`函数中，`i`指向当前正在计算next值的位置，`j`指向前一个字符的next值。如果当前字符匹配成功，则将`j`和`i`同时向右移动一位，并将当前位置的next值设为`j+1`；如果匹配失败，则通过next数组将`j`移动到下一个匹配位置。当`i`移动到模式串的末尾时，next数组计算完成。