演算法數據結構 | 只要30行程式碼，實現快速匹配字元串的KMP演算法

本文始發於個人公眾號：TechFlow，原創不易，求個關注


今天是演算法數據結構專題的第29篇文章，我們來聊一個新的字元串匹配演算法——KMP。

KMP這個名字不是影片播放器，更不是看毛片，它其實是由Knuth、Morris、Pratt這三個大牛名字的合稱。老外很喜歡用人名來命名演算法或者是定理，數學裡就有一堆，什麼高斯定理、歐拉函數什麼的。但是中國人更傾向於從表意上來給一個概念命名，比如勾股定理、同餘定理等等。之前覺得用人名命名很洋氣，作者可以青史留名，後來想想這也是英文表意能力不足，很難用表意的方式起名的體現。

扯遠了，我們回到正題。


應用場景


在電腦領域當中字元串匹配其實是一個非常常見的問題，我們使用它的場景也多到不可計數。比如在一個已經打開的頁面當中搜索關鍵詞，再比如說git裡面的程式碼變動的記錄，以及論文的查重等等。在這些問題當中有些情況可能還好，比如說我們搜索一個關鍵詞，因為關鍵詞並不長，我們暴力枚舉也不會特別耗時。但是在有些問題當中明顯暴力匹配是無法勝任的，比如論文查重。一篇論文動輒上千詞，要和庫中的上萬篇文章進行查重掃描，這當中的工作量可想而知。如果是暴力枚舉演算法那查重顯然會查到天荒地老。

所以早期的時候字元串匹配是一個難題，既然是難題那麼顯然就會有很多人來研究，也因此出了很多成果，很多大牛發表了字元串匹配的演算法，其中KMP演算法由於效率很高、實現複雜度低被應用得最廣。到這裡，我們就知道KMP演算法是用來字元串匹配的。

比方說我們有兩個字元串，A串是：I hate learning English. B串是hate learning，很明顯B串是A串的字元串。如果我們暴力枚舉來判斷的話，我們需要遍歷A串當中的每一個起始位置是否能夠完成匹配，那麼複雜度顯然是\(O(mn)\)。通過KMP演算法，我們可以在\(O(n)\)的時間內做到這點。

著名的大佬matrix67在KMP演算法的介紹部落格當中有一句著名的騷話，當你有一個喜歡的MM，你可以委婉地問她：「假如你要向你喜歡的人表白的話，我的名字是你的告白語中的子串嗎？」


Next數組


KMP演算法的核心精髓只有一個就是Next數組，但是這個概念並不太容易理解，很多人學KMP放棄就是折戟在了Next這個數組上。

我們先把Next數組是怎麼來的放在一邊，先來看下Next數組是用來幹嘛的，它起作用的原理是什麼，最後再來討論Next數組怎麼來的問題。根據我的理解，Next數組其實就是一個中途開始的機會，也就是當我們在枚舉匹配的時候，發現了不匹配的情況，我們不是從頭開始，而是從一個最大可能的中間結果開始。

我們來看個例子：

上圖中上面的是A串，下面的是B串，我們在匹配的過程當中發現B串的前面幾位都匹配上了，而在最後一位匹配失敗。按照常規的做法，我們應該是移動到下一個位置從頭開始匹配。但是這是非常浪費的，因為我們觀察下可以發現失敗位置的ABC和B串開頭的ABC是可以構成匹配的。

我們之前失敗的時候判斷的是以C結尾的ABCDABC和B串的匹配，在這一次匹配失敗之後，我們可以繼續嘗試匹配其他以C結尾的前綴串，比如ABC。這樣我們就可以從中間狀態開始，而節省了許多次不必要的枚舉。但問題就來了，這個中間結果是怎麼來的呢，我們怎麼知道當下失敗了上一個可行的中間結果是哪一個？

對，沒有錯，前面說到的Next數組就是用來存儲中間結果的。所以Next可以理解成下一次機會的意思，這樣就好理解了。由於我們是在A串當中尋找B串，所以這個Next數組應該是針對B的，記錄B中每一個位置如果匹配失敗，它的前面一個可行的中間狀態是哪一個。

我們先寫出來B的Next數組，等會再去研究它是怎麼得到的。為了簡化編碼，我們假設字元串是從1位置開始的，所以我們在0的位置添加一個$符號作為佔位符。對於大部分情況都是沒有重來的機會的，失敗了直接歸零。而其中的A和B兩個位置是有重來機會的，因為B的前綴當中出現了A和AB。所以如果在匹配ABD的時候失敗了，我們還可以從AB處再次開始嘗試匹配ABC。


演算法原理


我們想像一根指針指向了B數組當中接下來要匹配的位置，如果匹配失敗了，它就會跳轉到Next數組當中記錄的位置去，匹配成功了我們就向後移動一位。在有了Next數組之後，我們寫出程式碼來真的很容易了：

def kmp(var_str, template_str):
    # var_str即A串
    # template_str模式串即B串
    # 我們在兩個字元串前加上了佔位符
    var_str = '$' + var_str
    template_str = '$' + template_str
    next = generate_next(template_str)
    n, m = len(var_str), len(template_str)
    # head指向要匹配的位置的前一位
    head = 0
    for i in range(1, n):
        # 由於next數組很長，可能失敗多次
        # 直到head+1的位置能匹配上或者head等於0
        while head > 0 and template_str[head+1] != var_str[i]:
            head = next[head]
        
        # 匹配上了則head變長一位
        if template_str[head+1] == var_str[i]:
            head += 1
        
        # 如果head長度等於B串了，則表示匹配成功
        if head == m - 1:
            return True
    
    return False

對於A串中的每一個位置來說，我們都在B串當中遍歷了每一個有可能構成匹配的前綴。所以說這個演算法是可行的，一定可以獲得解。另外一個問題是複雜度的問題，為什麼我們用了兩重循環，但仍然是\(O(n)\)的演算法呢？

其實很簡單，因為while循環只會讓head減小，而不會讓head增加。head增加是在for循環里執行的，也就是說head最多增加n次。那麼對應的while循環也就最多執行n次，因為head是非負的。所以while循環在整個for循環執行的過程當中最多執行了n次，整體執行的次數仍然是\(O(n)\)級別的而不是\(n^2\)級，當然是線性的演算法。


求解Next


到這裡，問題只剩下了一個，就是這個Next怎麼來呢？

其實我們在之前講Next數組的使用的時候已經泄露天機了，我們再來看下上圖，不知道大家能感覺到什麼。

後面一個A的Next值是1，也就是第一個A的下標，後面一個B的Next值是2，也就是第一個B的下標。換句話說第二個A能夠和位置1的A匹配，後面的AB能和前綴的AB匹配。也就是說Next數組其實就是B數組自己和自己匹配的結果，我們在一開始的時候將整個Next數組全部置為0，然後依次遞推迭代出所有的Next的值。

我們在求解Next[i]的時候我們可以利用上Next[i-1]的值，因為Next[i-1]存儲的是能夠與B[i-1]匹配的前綴的結尾位置。如果B[Next[i-1]+1]等於B[i]，那麼說明Next[i] = Next[i-1] + 1。如果不等的話，我們可以用while循環來尋找能夠匹配上的前綴。也就是說這是一個遞推的過程，不過要注意一點我們計算Next數組要從2開始，因為對於1來說，Next[1]一定等於0。

def generate_next(var_str):
    n = len(var_str)
    next = [0 for _ in range(n)]
    for i in range(2, n):
        # 用next[i-1]作為開始尋找能夠匹配上的最長next[i]
        head = next[i-1]
        while head > 0 and var_str[head+1] != var_str[i]:
            head = next[head]
		
        # 如果匹配上了，head+1
        if var_str[head+1] == var_str[i]:
            head = head + 1
        # 記錄下來
        next[i] = head
    return next

總結


到這裡，我們關於KMP演算法的介紹就結束了，不知道大家看完之後感受如何，是不是有點蒙圈呢？

其實蒙圈是正常的，我第一次學的時候足足看了好幾遍才算是看明白。這畢竟是一個比較巧妙的演算法，想要通過閱讀一篇文章就完全學會還是比較困難的，最好的還是親自動手實現一下試試。KMP演算法我最大的感受就是如果你把整個演算法的邏輯都串起來了，那麼即是自己從頭到尾推導一遍難度也不是很大（我就在面試當中推導過一次）。如果你沒能把邏輯串起來，那麼覺得難理解看不懂是正常的，你可能需要再讀一遍或者是尋找一些其他的資料查漏補缺。

今天的文章到這裡就結束了，如果喜歡本文的話，請來一波素質三連，給我一點支援吧（關注、轉發、點贊）。

Tags:

VirMach 便宜 VPS