kmp算法next表

kmp算法的next表

def getNext(p):
    next = {}
    next[1] = 0
    i, j = 1, 0
    while(i < len(p)):
        if j == 0 || p[i] == p[j]:
            i += 1 # suffix
            j += 1 # prefix
            if p[i] != p[j]:
                next[i] = j
            else:
                # 如果前缀相同，则回溯到j的next值
                next[i] = next[j]
        else:
            # j回溯
            j = next[j]
    return next