说明

代码

def compute_prefix_func(P):
    m = len(P)
    pi = [0] * m
    k = 0
    for q in range(1,m):
        while k > 0 and P[k] != P[q]:
            k = pi[k-1]
        if P[k] == P[q]:
            k=k+1
        pi[q] = k
    return pi
def kmp_match(T, P):
    n = len(T)
    m = len(P)
    q = 0
    pi = compute_prefix_func(P)
    for i in range(n):
        while q > 0 and P[q] != T[i]:
            q = pi[q-1]
        if P[q] == T[i]:
            q=q+1
        if q == m:
            return i-m+1
    return -1
a = kmp_match('xxxxgdagexxxx','gdage')
print(a)