在Python中实现KMP算法

def generate_partial_match_table(pattern):
    table = [0] * len(pattern)
    i, j = 1, 0
    while i < len(pattern):
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
            i += 1
        else:
            if j > 0:
                j = table[j-1]
            else:
                table[i] = 0
                i += 1
    return table

def kmp_search(text, pattern):
    m, n = len(text), len(pattern)
    if n == 0:
        return 0
    if m < n:
        return -1

    table = generate_partial_match_table(pattern)
    i, j = 0, 0
    while i < m:
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == n:
                return i - j
        else:
            if j > 0:
                j = table[j-1]
            else:
                i += 1
    return -1

text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
index = kmp_search(text, pattern)
if index != -1:
    print("Pattern found at index", index)
else:
    print("Pattern not found")