Python实现KPM算法详解

def GetNext(t, next):
    j, k = 0, -1
    next[0] = -1
    while j < len(t) - 1:
        if k == -1 or t[j] == t[k]:  # 如果k==-1 或者 开始位置和结尾位置有相同的元素
            j, k = j + 1, k + 1  # j和k都加1,当前位匹配，则从下一个位置开始匹配，所以k+1；j再进行取下一位判断是否也是匹配，所以也要+1
            next[j] = k  # 当前位置要取k项
        else:#如果不相等，再把k置-1，下一次循环再进行+1操作，j这个位置再存入0，表示无匹配项
            k = next[k]
    return next

def KMP(s, t):
    next = [0] * len(t)
    next = GetNext(t, next)
    print(next)
    i, j = 0, 0
    while i < len(s) and j < len(t):
        if j == -1 or s[i] == t[j]:
            i, j = i + 1, j + 1
        else:
            j = next[j]
    if j >= len(t):
        return i - len(t)
    else:
        return -1

def GetNext(t, next):
    j, k = 0, -1
    next[0] = -1
    while j < len(t) - 1:
        if k == -1 or t[j] == t[k]:  # 如果k==-1 或者 开始位置和结尾位置有相同的元素
            j, k = j + 1, k + 1  # j和k都加1,当前位匹配，则从下一个位置开始匹配，所以k+1；j再进行取下一位判断是否也是匹配，所以也要+1
            next[j] = k  # 当前位置要取k项
        else:#如果不相等，再把k置-1，下一次循环再进行+1操作，j这个位置再存入0，表示无匹配项
            k = next[k]
    return next
 
 
def KMP(s, t):
    next = [0] * len(t)
    next = GetNext(t, next)
    print(next)
    i, j = 0, 0
    while i < len(s) and j < len(t):
        if j == -1 or s[i] == t[j]:
            i, j = i + 1, j + 1
        else:
            j = next[j]
    if j >= len(t):
        return i - len(t)
    else:
        return -1
 
 
if __name__ == '__main__':
    re = KMP('asdfghjsssaaasdfaaaabababcdabd', "ababaaaababaa")
    print(re)