關于Python中KMP算法分析

這篇文章主要介紹關于Python中KMP算法分析，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！

暴力匹配(BF)

字符串匹配是我們在編程中常見的問題，其中從一個字符串(主串)中檢測出另一個字符串(模式串)是一個非常經典的問題，當提及到這個問題時我們首先想到的算法可能就是暴力匹配，下面的動圖就展示了暴力匹配的流程。

上圖中箭頭指向的字符都為藍色時代表二者匹配，都為黑色時代表二者不匹配，紅色則代表在主串中找到模式串。

這種算法大致思路就是每當模式串和主串中有字符不匹配，模式串與主串對應的位置整體向后移動一位，

再次從模式串第一位開始比較，重復上述做法直至在主串中匹配到模式串或者匹配到主串最后一位結束。

如果主串與模式串都比較短時，用暴力匹配還是不錯的選擇，編碼也相對容易；

但是如果主串與模式串過長時，我們只是簡單想想就知道這個過程是非常耗時的，那么會不會有對應的優化算法呢？

下面就介紹本文的主角——KMP算法，不扯沒用的概念，直接講算法的應用過程及利用Python實現該算法的代碼，最后會通過二者時間復雜度的分析，總結出為何KMP算法會優于暴力匹配算法。

KMP算法

構建前綴表

我們首先要確定一下引例的主串和模式串：

主 串 S = “abacaababc”

模式串P=“ababc”

在模式串與主串匹配時，我們暫時只看第4步，明顯主串S中的c和模式串P中的b是不匹配的：

如果用暴力匹配算法，那么就是后移模式串P，在從P的第一個字符開始比較。但是現在通過匹配我們可以知道的是當第4位不匹配時，前三個字符為"aba"是確定的，這個已知信息是十分有用的。

而KMP算法的核心就是利用匹配失敗后獲取的信息，盡量減少模式串與主串的匹配次數以達到快速匹配的目的，比如對于這個不匹配現象我們是不是可以直接這樣移動模式串呢？

那么信息從何而來呢？在KMP算法中，對于一個模式串都可以先計算出其內部的匹配信息，這樣在匹配失敗時可以最有效的移動模式串，從而減少匹配次數。在此之前，需要先理解一下前綴和后綴。

前綴：abcde的前綴可以是a、ab、abc、abcd

后綴：abcde的后綴可以是e、de、cde、bcde

這里需要引出一個新的概念——前綴表，可以用profix表示、且下標從0開始，profix[i]存儲的信息就是前i+1個字符的最長公共前后綴，并且這個最長公共前后綴長度一定是小于字符串長度的。

可以看到"ababc"不是前后綴，但也被列到了表中。

如果你曾經了解過KMP算法，那你可能聽過next數組，當前綴表轉化為next數組時，最后一位的值會被覆蓋掉，對過程是沒有什么影響的。

由于本文僅是靠著前綴表profix完成KMP算法，所以不再過多講述next數組，不同的方法只是表示形式不一樣，但歸根結底原理還是相同的。

上面的前綴表是我們通過肉眼比對得出的，程序畢竟不是人嘛，所以需要通過一種程序能夠識別的方法構建前綴表，依據下圖進行講述流程。

通過這個圖可以將構建前綴表規劃成下面五步：

2、首先創建兩個指針，指針j指向模式串第一位(下標為0)、指針i指向模式串第二位(下標為1)。

2、由于模式串最開始是單一字符，沒有前綴和后綴，所以對應前綴表第一位總為0。

3、當j=0時，比較j和i指向的字符，如果字符不匹配，i對應的前綴表位置填入0，且將i向后移動移位，j原地不變。

4、當j和i指向的字符匹配時，i對應的前綴表位置填入(j+1)，且將j和i都后移一位。

5、如果j和i指向的字符不匹配，并且此時j≠0，j需要回溯到profix[j-1]的位置，

再次與i指向的字符比較，重復此步驟直至j和i指向的字符匹配或者j=0。

當結合圖讀完這五個步驟時，我猜你會不理解第五步，如果你都理解了，我也只能感嘆一句NiuBi，利用下面這個例子更能凸顯出步驟五的回溯機制。

依據上面步驟我寫出了前綴表的前五位，而此時j和i指向的字符不匹配且j≠0，這里j的下標是3，所以需要在前綴表中找到下標為j-1的值，即profix[2]，然后將j回溯到對應的位置。

這樣回溯是因為可以在模式串頭部找到和j和i之間的字符串相匹配的前綴，也就是這個例子中的a，如果此時j和i指向的字符相匹配，那么最長公共前后綴的長度就是已匹配的前綴的長度(a)再加1。由此可見如果j和i之間字符串很長時，這個操作可以節省很多時間。

而此時j和i指向的字符仍然不匹配，那么需要繼續回溯j，方法和上述一致，回溯的位置就是profix[0]。

此時j和i指向的字符還是不匹配，但這里需要做的就不是回溯了，因為j=0已經滿足回溯結束條件，只需將i對應前綴表的位置(profix[5])中填入0即可，用肉眼匹配也會發現此時的確沒有公共前后綴。

在理解上述步驟之后，可以將其當成偽代碼，依據偽代碼很容易編寫出構建前綴表函數。

def PrefixTable(Pattern):
    i = 1;j = 0
    prefix = [0]*len(Pattern)
    while(i<len(Pattern)):
        if Pattern[j]==Pattern[i]:
            prefix[i] = j+1
            j+=1;i+=1
        else:
            if j == 0:
                prefix[i] = 0
                i+=1
            else:
                j = prefix[j-1]
    return prefix

可以輸入一個模式串，測試一下該代碼是否能夠得出對應前綴表。

優化前綴表

經過上文解釋你可能會發現一個基本事實，即前綴表最后一位沒有任何作用，這么說的理由是什么呢？因為當j和i指向的字符不匹配時，這里的解決辦法是回溯j，而回溯依據一直都是prefix[j-1]，j是永遠不可能超越i的，所以前綴表最后一位永遠也不會用到。

那么最后一位就可以去掉，將所有元素整體后移一位，并向前綴表第一位填入-1，如下圖：

填入-1這個操作的原理等下結合圖片一起講述會更易懂，目前我們只需知道這個操作并且了解其對應代碼即可。

def MoveTable(prefix):
    for i in range(len(prefix)-1,0,-1):
        prefix[i] = prefix[i-1]
    prefix[0] = -1
    return prefix

KMP匹配機制

主串和模式串還是利用上文所舉例子，這里省略了一些簡單的匹配過程，直接看關鍵點。

可以看到主串和模式串的第4位是不匹配的，現在需要做的是將Pattern[prefix[4]]對應主串中需要匹配的元素，也就是模式串下標為1的元素后移至與主串第4位對應的位置，看圖可懂。

對應位置仍然不匹配，需要繼續后移模式串，該位置對應前綴表的值為0，所以將Pattern[prefix[0]]對應主串中需要匹配的元素，即模式串下標為0的元素與主串該位置對應。

此時兩串對應位置還是不匹配，但是a已經是模式串的第一位元素了，如果按照上面方法需要繼續后移模式串，讓主串那個位置與模式串下標為-1的元素匹配，可是前綴表中并不存在下標為-1的元素。

所以比較時如果模式串和主串對應位置不匹配，且模式串的元素對應前綴表的值為-1，那么直接將模式串整體后移一位，并且將指向主串的指針后移一位即可，這也是為什么在前綴表第一位插入-1的原因。

下面圖是利用KMP算法在主串中查找模式串的全過程。

KMP算法的代碼如下：

def KMP(TheString,Pattern):
    m = len(TheString);n = len(Pattern)
    prefix = PrefixTable(Pattern)
    prefix = MoveTable(prefix)
    i = 0;j = 0#i為主串指針，j為模式串指針
    while(i<m):
        if j==n-1 and TheString[i]==Pattern[j]:
            print("已在主串下標%d處找到模式串" % (i-j))
            j = prefix[j]
        if TheString[i]==Pattern[j]:
            i+=1;j+=1
        else:
            j = prefix[j]
            if j==-1:
                i+=1;j+=1

這里只講一下第一個if語句，當j指向了模式串最后一位，并且此時如果主串和模式串對應位置匹配，則代表在主串中找到了模式串，并打印出第一個字符出現的位置。

而j=prefix[j]j = prefix[j]j=prefix[j]這個語句的作用是在找到模式串后繼續匹配剩余的主串，因為可能會有主串中含有若干個模式串的現象出現。

最后整個程序運行截圖如下：

BF與KMP比較

為什么KMP會優于BF，這里通過對比二者的時間復雜度給出原因，假設有這么兩個比較極端的主串和模式串：

主 串 S = “aaaaaaab”

模式串P=“aaab”

首先看一下BF算法解決該匹配問題的流程：

然后再看一下KMP算法解決該匹配問題的流程：

假設主串長度為m，模式串長度為n。對于BF算法，每當遇到不匹配字符時，都要從模式串開頭再次匹配，所以對應時間復雜度O(m?n)O(m*n)O(m?n)；

對于KMP算法，每當遇到不匹配字符時，根據獲得的信息它不會重復匹配的已知前綴，所以對應時間復雜度為O(m+n)O(m+n)O(m+n)。當字符串較長時，就時間復雜度而言KMP算法是完全優于BF算法的。

以上是關于Python中KMP算法分析的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注億速云行業資訊頻道！