Python KMP算法

"""
思路：
1、建立next_list,next_list[i]表示当pattern[i]不匹配时，跳转的pattern最大公共区域的下一级值。
"""

s = 'abdabdabababaaababac'
p = 'ababaaababac'
lens, lenp = len(s), len(p)


def build_next():
    next_list = [0] * lenp
    for i in range(1, lenp):
        if p[i] == p[next_list[i - 1]]:
            next_list[i] = next_list[i - 1] + 1
    return next_list


def kmp_match():
    i = 0
    j = 0
    next_list = build_next()
    while i < len(s):
        if lens - i >= lenp - j:
            if s[i] == p[j]:
                i += 1
                j += 1
            elif j == 0:
                i += 1
            else:
                j = next_list[j - 1]
        else:
            return -1
    return lens - j


print('next_list: ', build_next())
print('match_at: ', kmp_match())