KMP字串對比演演算法及next陣列計算

　　（注：該貼主要運用python實現該演演算法）

　　先談談KMP演演算法吧。KMP演演算法的全稱是Knuth-Morris-Pratt 演演算法，它是用來進行字串查詢，即在某個主字串裡面找到某個特定子字串。但是好像這個問題也可以直接暴力查詢來完成啊，可是暴力查詢的的缺點是不可忽視的：它的時間複雜度太高了！一旦遇見長的字串就會讓程式執行時間指數型增長。而用KMP演演算法可以很好的解決程式碼的時間複雜度高的問題，它的時間複雜度是線性的，也就是說該演演算法的時間複雜度取決於兩個字串的長度。

　　接下來我會對KMP演演算法完成任務的大概思路進行敘述

　　首先，我們約定一些符號：S為主字串，也就是被進行查詢的字串；P為子字串，也就是需要查詢的字串；next為next陣列，裡面記錄了一些解決任務的關鍵資訊，這裡先買一些關子，畢竟比較難解釋。

　　然後就是給定一個主字串S = ‘ACBACC DBACBACDEA’，子字串P = ‘ACBACD’，next = [-1, 0, 0, 0, 1, 2]

　　接著開始比對

 　　如上圖，當i = 0，j = 0時，二者相等，所以i和j皆進一位；

　　　　　　 當i = 1，j = 1時，二者相等，所以i和j皆進一位；

　　　　　 　當i = 2，j = 2時，二者相等，所以i和j皆進一位；

　　　　　 　當i = 3，j = 3時，二者相等，所以i和j皆進一位；

　　　　　 　當i = 4，j = 4時，二者相等，所以i和j皆進一位；

　　　　　　 當i = 5，j = 5時，二者不相等，所以把j = next[j] = 3，i不變；

（箭頭表示當前在比較的位置）

　　　　　　 當i = 5，j = 2時，二者相等，所以i和j皆進一位；

　　　　　　 當i = 6，j = 3時，二者不相等，所以把j = next[j] = 0，i不變；

（箭頭表示當前在比較的位置）

　　　　　　 當i = 6，j = 0時，二者不相等，所以把j = next[j] = -1，i不變；

　　　　　　 當i = 6，j = -1時，此時j為特殊值，所以i和j皆進一位；

　　　　　　 當i = 7，j = 0時，二者不相等，所以把j = next[j] = -1，i不變；

　　　　　　 當i = 7，j = -1時，此時j為特殊值，所以i和j皆進一位；

　　　　　　 當i = 8，j = 0時，二者不相等，所以把j = next[j] = -1，i不變；

　　　　　　 當i = 8，j = -1時，此時j為特殊值，所以i和j皆進一位；

（箭頭表示當前在比較的位置）

 　　　　　　當i = 9，j = 0時，二者相等，所以i和j皆進一位；

 　　　　　　當i = 10，j = 1時，二者相等，所以i和j皆進一位； 

　　　　　　 當i = 11，j = 2時，二者相等，所以i和j皆進一位；

 　　　　　　當i = 12，j = 3時，二者相等，所以i和j皆進一位；

 　　　　　　當i = 13，j = 4時，二者相等，所以i和j皆進一位； 

　　　　　　 當i = 14，j = 5時，二者相等，所以i和j皆進一位；

 　　　　　　當i = 15，j = 6時，此時檢測到j>len(P)了，則跳出迴圈；

　　　　　　 最後返回布林值，或者返回你想要得到的資訊

　　如此，我們就走完了一次KMP演演算法，完成了一次任務，得到了正確的結果

　　通過上面的流程，我們可以得知KMP演演算法中有一個重要的部分：next陣列。

　　那next陣列是什麼呢？next陣列主要用於儲存j位之前的字串的最長相同字首和字尾的長度。

（

　　什麼是字首、字尾呢？"字首"指除了最後一個字元以外，一個字串的全部頭部組合；"字尾"指除了第一個字元以外，一個字串的全部尾部組合。當然，這裡指的是在j位之前包括j位的前字尾。

　　需要注意的是：假如有一個字串「abcd」，那麼其字首是：a ab abc，其字尾是：bcd cd d。也就是說前字尾是不止一個的。

　　而前文所說的最長相同字首和字尾的長度即是指：假若有一個字串「aabab」，其字首是：a aa aab aaba，其字尾是：aaba aba ba a，那這個的最長相同前字尾是a，所以該位置對應next陣列的位置的值的應該是1。

　　練習：「abcabx」  [0,0,0,1,2,0]

　）

　　這裡提供一個程式碼計算next陣列的方法

def get_next(son_str: str) -> list():
    """
    獲得next陣列

    引數解釋 son_str: 需要求next陣列的字串
    返回值: 返回next陣列
    """
    length = len(son_str)

    # 定義next陣列
    next = length*[None]
    next[0] = -1
    next[1] = 0

    # 計算next陣列
    k = -1
    j = 0
    while j < length-1:
        if son_str[k] == son_str[j] or k == -1:
            j += 1
            k += 1
            next[j] = k
        else:
            k = next[k]
    return next

　　這裡的next[0] = -1主要是因為方便程式碼處理j回到0時，發現S[i] != P[j]時，i無法進位的情況（用上面第一個方法求出的next陣列也可用，但是具體方法得去搜尋了，作者是使用的是程式碼求出來的那個next陣列）

　　到此，該演演算法也已經講得差不多了

　　下面提供完整的程式碼

#!/usr/bin/env python
# -*- encoding: utf-8 -*-
'''
@檔名     : KMP.py
@描述     :   實現KMP演演算法，進行字串比對 
@建立時間     : 2023/09/07/20
@作者     : zrold
@版本     : 1.0
'''


def kmp(farther_str: str, son_str: str) -> bool:
    """
    定義KMP演演算法, 並根據傳進來的兩個引數來進行比對, 並返回一個布林值

    引數解釋: farther_str: 進行比對的主字串, 
              son_str: 子字串
    返回值: 返回一個布林值
    """
    # 得到next陣列
    next = get_next(son_str)

    # 匹配字串
    i = 0
    j = 0
    while i < len(farther_str) and j < len(son_str):
        if farther_str[i] == son_str[j] or j == -1:
            i += 1
            j += 1
        else:
            j = next[j]

    if j >= len(son_str):
        return True
    else:
        return False


def get_next(son_str: str) -> list():
    """
    獲得next陣列

    引數解釋 son_str: 需要求next陣列的字串
    返回值: 返回next陣列
    """
    length = len(son_str)

    # 定義next陣列
    next = length*[None]
    next[0] = -1
    next[1] = 0

    # 計算next陣列
    k = -1
    j = 0
    while j < length-1:
        if son_str[k] == son_str[j] or k == -1:
            j += 1
            k += 1
            next[j] = k
        else:
            k = next[k]
    return next


if __name__ == '__main__':
    farther_str = input('請輸入需要進行對比的主字串:')
    son_str = input('請輸入需要在主字串中找到的子字串:')
    if kmp(farther_str, son_str):
        print(f'確實存在"{son_str}"在"{farther_str}"中')
    else:
        print(f'不存在"{son_str}"在"{farther_str}"中')