KMP算法

def KMP(s, p):
    nex = getNext(p)
    i, j = 0, 0  # 分别是s和p的指针
    while i < len(s) and j < len(p):
        if j == -1 or s[i] == p[j]:  # j==-1是由于j=next[j]产生
            i += 1
            j += 1
        else:
            j = nex[j]

    if j == len(p):  # 匹配到了
        return i - j
    else:
        return -1

def getNext(p):
    nex = [0] * len(p)
    nex[0] = -1
    i = 0
    j = -1
    while i < len(p) - 1:  # len(p)-1防止越界，因为nex前面插入了-1
        if j == -1 or p[i] == p[j]:
            i += 1
            j += 1
            nex[i] = j  # 这是最大的不同：记录next[i]
        else:
            j = nex[j]

    return nex

• 参考文献
  1.B站灯笼哥
  2.KMP算法python实现
  3.如何更好的理解和掌握 KMP 算法?