根據算法導論實作KMP算法(python 3)

在我看來阮一峰的字元串比對的KMP算法 對于入門挺好,但是對于KMP的實作很不友好,被繞進去了很多次.

始終覺得<算法導論>裡面的方法更加簡潔一點,雖然需要自己花點時間演算一下才能了解.

#計算next數組
def compute_prefix(p):
    m = len(p)
    res = [- for _ in range(m)]#置-1作為沒有找到比對字首的标志
    res[] = -
    k = -
    for q in range(,m):
        while k > - and p[k+]!=p[q]:
            k = res[k]#若失位,在已比對到的資訊中找.(若得到-1,會跳出循環)
        if p[k+] == p[q]:
            k = k + 
        res[q] = k
    return res

#KMP比對過程
def kmp_matcher(t,p):
    n, m = len(t), len(p)
    nxt = compute_prefix(p)#得到next數組
    q = -
    for i in range(n):
        #若失位的操作
        while q > - and p[q+] != t[i]:
            q = nxt[q]
        #從失位恢複處或p最左端繼續比對
        if p[q+] == t[i]:
            q = q + 
        #當p字元串的下标q達到m-1時,意味着比對成功,找到一個目标pattern
        if q == (m - ):
            #輸出pattern起始位置
            print("Pattern occurs with shift ",i-m+)
            #繼續在t中尋找下一個pattern
            q = nxt[q]
           

#測試
p = "ababababca"
# t中藏了兩個ababababca
t = "vhjvgdhacvjchacvajcbcababababcahvcdakcacbcbajhcacvacgacahcjachascababababca"
kmp_matcher(t,p)
           

Pattern occurs with shift  
Pattern occurs with shift  
           

在電話面試裡遇到了KMP算法, 算是之前看過也了解過, 但是沒有仔細去真正實作過,或許KMP本身不太适合作為電話面試的題目,也或許是自己的表達能力還未到水準,腦裡對KMP的概念難以用語言表達出(最長公共前字尾? 實作O(m+n)? next數組? 似乎幾個關鍵詞都難以表達對KMP的了解)

網上對KMP的現實有很多,但是在我看來,在計算next數組的部分應該要達到O(m)級别的,看了一下很多人的做法都是用python set集合或者周遊以一個O(m*m)作為解決方案,是不夠準确的. 對于KMP的細究還是有必要的, 如果不細究早就用樸素比對解決了, 哪裡還用得着設計一個KMP.

另一個要點是入門一個算法,第一步是抽象想象,能以一個動畫想象算法過程.第二步是以一個執行個體用紙筆演算一次. 加上最後的實作,基本可以掌握一個算法的70%了.

附上一張截圖幫助了解next數組的計算.