def prefix_table(pattern, prefix,  n):
  #  prefix = [0]*n
    i = 1
    length = 0 # 代表公共前后缀的长度
    while i < n:
        if pattern[i] == pattern[length]:
            length += 1
            prefix[i] = length
            i += 1
        else:
            if(length > 0):
                length = prefix[length-1]
            else:
                prefix[i] = length
                i += 1  #这边解决刚开始两个就不相等

def move_prefix(prefix, n):
    for i in range(n-1, 0, -1):
        prefix[i] = prefix[i-1]
    prefix[0] = -1


def kmp_search(text, pattern, n):
    prefix_table(pattern, prefix, n)
    move_prefix(prefix, n)
    m = len(text)
    #text[i], 长度为m
    #pattern[j], 长度为n
    i , j =0, 0
    while i < m:
        if j == n-1 and text[i] == pattern[j]:
            print("found %d", i-j)
            j = prefix[j]

        if text[i] == pattern[j]:
            i += 1
            j += 1
        else:
            j = prefix[j]
            if j == -1:
                i += 1
                j += 1

if __name__ == "__main__":
    pattern = "ABABCABAA"
    n = len(pattern)
    prefix = [0]*n
    prefix_table(pattern, prefix, n)
    for i in range(len(prefix)):
        print(prefix[i])
    move_prefix(prefix, n)
    for i in range(len(prefix)):
        print(prefix[i])
    text = "BABABCABAACDF"
    kmp_search(text, pattern, n)

KMP算法