用Python实现kmp算法

KMP算法（Knuth-Morris-Pratt算法）是一种字符串匹配算法，可以在O(n+m)的时间复杂度内实现字符串匹配，其中n和m分别为文本串和模式串的长度。以下是Python实现KMP算法的代码：

def kmp(text, pattern):
    n = len(text)
    m = len(pattern)
    if m == 0:
        return 0
    if n < m:
        return -1
    lps = computeLPS(pattern)
    i = 0
    j = 0
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == m:
            return i-j
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = lps[j-1]
            else:
                i += 1
    return -1

def computeLPS(pattern):
    m = len(pattern)
    lps = [0] * m
    i = 1
    j = 0
    while i < m:
        if pattern[i] == pattern[j]:
            j += 1
            lps[i] = j
            i += 1
        elif j != 0:
            j = lps[j-1]
        else:
            lps[i] = 0
            i += 1
    return lps

其中，computeLPS函数实现了计算模式串的最长公共前后缀长度数组。kmp函数中，首先判断模式串是否为空或者文本串长度小于模式串长度，然后计算出模式串的最长公共前后缀长度数组lps。接着，用双指针i和j分别指向文本串和模式串的起始位置，进行匹配。如果当前字符匹配成功，则i和j都向前移动一位，如果匹配失败，则j回退到lps[j-1]的位置。如果j等于模式串长度m，则说明匹配成功，返回文本串中匹配的起始位置i-j。如果整个循环结束都没有匹配成功，则返回-1。