記錄對KMP算法的一些了解
釋意：
- mstr：目标串；主串
- pstr： 模式串
首先，要介紹看毛片KMP算法，就得先介紹什麼是字元串比對算法；
給出問題：給定主串mstr（eg：abababbaaaba）和模式串pstr（eg：bba），如何判斷主串中是否含有模式串？
類似這種，判斷字元串pstr是否存在于另一字元串mstr中的問題，就是字元串比對問題；
碰到這類問題，如果是簡單/短一些的字元串，可以直接考慮使用暴力比對法：
轉換為代碼，
# 暴力比對法
def bfMatching(mstr, pstr): # mstr：目标串，pstr：模式串
mLen, pLen = len(mstr), len(pstr) # 記錄兩串長度
i, j = 0, 0 # 初始化兩串比對索引值
while i < mLen and j < pLen: # 終止循環條件
if mstr[i] == pstr[j]: # 字元比對成功
i, j = i + 1, j + 1 # 兩串索引均向前行進
else: # 字元串失配
i, j = i - j + 1, 0 # 模式串索引跳轉至首位，目标串索引跳轉至本輪比對首字元的下一位
if j == n: # 模式串行進結束，即比對成功
return i - j # 傳回主串中比對字串首字元位置
return -1 # 比對失敗
從了解上來說，可以看作是在目标串mstr上逐位向後推進，即以mstr上每一位字元為基準，與模式串pstr進行比對；
我想，這從邏輯上了解并不難；
由于暴力比對法的時間複雜度為O(n2)，如果目标串很長，模式串也很長，暴力比對法的時間資源消耗是巨大的；
KMP算法
其實，在字元串比對的過程中，有很多細節值得考究，上文的圖中，由于模式串過短，不容易看出，我們再來張圖，你應該能看出些端倪：
子串比對到最後一個字元，與目标串失配，那麼，按照暴力比對的思路，是将模式串向右移一位，從新開始比較字元串，如下示：
模式串右移一位後，繼續失配、失配、失配...，直到模式串右移的第四次，與目标串完美比對：
讓我們回到此次比對的第一次循環，即模式串前6個字元比對，在第六個字元“m”處失配；
試想，在比對過程中，模式串是不是已經擷取到目标串的很多資訊，例如，模式串失配字元前的字元‘ab’與模式串前兩個字元‘ab’相等；
那可不可以在第一次失配後，直接将模式串前兩個字元‘ab’移動到目标串失配字元前兩個字元‘ab’處？（此處，目标串失配字元前是字元‘ab’，這是可以确定的），當然可以，這就是KMP算法的思想，同時，這種思想涉及到求取字元串的最大相等字首字尾以及next數組；
子串最長相同字首字尾
什麼是最長相同字首字尾？
我也不打算用文字或者公式來叙述，用圖來了解更直覺些
好了，現在你已經了解什麼是子串最長相同字首字尾了，這對了解KMP算法中的next數組很有幫助；
next數組及其求取
next數組的概念與前文所述子串最大相同字首字尾息息相關；
不同的是，next數組是存放字元串中每一字元（不包括）前最大相同字首字尾長度的數組，記住，數組存放的是長度（int類型），而不是字元（string類型）。
以表說明：
這下你應該了解next數組了把，注意，next數組首位置為-1，目的是友善代碼編寫；
了解了這些基本概念，那我們來試試讓程式幫我們求對應字元串的next數組把，我先把代碼貼上來：
def genPnext(pstr): # 傳入模式串
pLen = len(pstr) # 擷取長度值
pnext = [-1] * pLen # 初始化next表
i, j = -1, 0 # j沿單方向朝模式串尾部行進；i索引記錄已比對資訊，用于回溯
while j < pLen - 1: # 設定循環條件，j行進至串尾部結束循環
if i == -1 or pstr[i] == pstr[j]: # 右側條件真，則在上一輪比對基礎上，在pnext表下一空位置值增加1
# 左側條件為i回溯終止條件，即回溯至記錄資訊量歸零
i, j = i + 1, j + 1 # 資訊比對，j向前行進，i增加已比對資訊
pnext[j] = i # pnext新空位值較前位值增加1（基于i，j值比對條件上）
else:
i = pnext[i] # i，j處字元失配，j停止向前，i向已記錄最長字首字尾處跳轉
# print(pnext)
return pnext
乍的一看，有點懵，看看注釋，emmm，好像更懵；
沒關系，我們繼續用圖來說明，具象點觀察代碼每一步的作用以及原理；
規定字元串名稱為：str
為保證i與j分開向串的尾部行進，初始化i = -1，j = 0（程式員數數都是從0開始，這沒疑問吧~）；
職能上看，i 索引負責管理比對中字首新字元，j 索引負責管理比對中字尾新字元；
j 索引用于确定每個字元的next數組值，即next[j]，而 i 索引用于每次字元失配後進行回溯，查詢記錄中最大相同字首字尾長度并跳轉過去，再次與str[j]進行比對（這裡是每次用 str[j] 與 str[i]比較，處理後得出的結果填在next[j+1]處，不明白就瞅一眼代碼吧）；
next的求取是向前遞進的，請留意，已得的next數組包含很大的資訊量，後方字元next值的求取會非常倚重前方已得的字元next值；
接下來，我們進入正題：
1、向串尾部行進的過程中，如果str[i]==str[j]，那麼認為較上一字元str[j-1]的next值next[j-1]，字元str[j]的next值next[j]增加了1，這是基于已得next數組資訊的基礎上得出的（每一輪對next值的求取，主要觀察的是j索引指向的新字元，如果比對，那麼基于前一輪得出的最大相同字首字尾長度，這一輪加1就好，下給圖示）
2、如果str[i]！=str[j]，有意思的來了，i值需要立即回溯到位置0嗎？也不能斷定說不需要，萬一next[i]=0呢。這裡傳達的意思是，當新字元失配時，i 需要利用已取得的next數組，回溯到合适的位置；
目前字元失配，那麼 j 立在原地不用動，i 根據 i = next[i]跳轉到相應位置，原理是 i 位置雖然與 j 位置失配，但是仍然可能有相同的字首、字尾，這裡視既得next數組而定，我們可能還需要一張圖來說明：
現在再或過頭看看代碼，是不是有不一樣的感覺了？
KMP算法實作
老規矩，我先貼個代碼哈
# KMP比對算法
def kmpMaching(mstr, pstr): # mstr：主串；pstr：模式串
pnext = genPnext(pstr) # 根據模式串求取pnext數組
pLen, mLen = len(pstr), len(mstr) # 記錄主串/模式串長度
i, j = 0, 0 # 主串/模式串索引指針初始化
while j < mLen and i < pLen: # 設定循環邊界條件
if i == -1 or mstr[j] == pstr[i]: # 右側條件真，則相應位置字元比對成功
# 左側條件為失配後模式串回溯的終止條件，即失配後未在模式串中找到合适子串（最大字首字尾）
i, j = i + 1, j + 1 # 向前行進
else:
i = pnext[i] # 字元失配，模式串索引指針跳轉至已記錄最大比對子串
if i == pLen: # 模式串比對完成
return j - i # 傳回主串中比對字串首字元位置
return -1 # 比對失敗
緊接着，我們用圖來說明，
以上，
文章不那麼深入同時也不那麼嚴謹，隻是以簡單的方式表述出作者對kmp算法的了解與拙見，希望能夠幫助迷惑時的你。