假設有一個需求，需要我們從串“a b a b c a b c a c b a b"中，尋找内容為“a b c a c”的子串。
此時，稱“a b a b c a b c a c b a b"為主串S，“a b c a c”為模式串T。
很容易想到，通過周遊主串S，與模式串T的首字母逐一比對，當主串S中的某一進制素i與模式串T首字元j相同，則将主串S中第i+1個字元與模式串T的j+1個字元繼續比對。若比對成功，則繼續将主串S中的第i+2個字元與模式串T中的第j+2個字元進行比對。若比對失敗，則将主串S的第i+1個字元與模式串的第j個字元重新比對....
将上述文字轉化為圖像如下：
按照動畫的顯示效果很容易了解BF模式比對算法。
通過分析可以得出，每次比對失敗之後，i的指向又将回到主串S的i-j+2位置
通過C語言僞代碼的方式實作：
若将主串S的長度看作m，将模式串T的長度看作n
則該代碼的時間複雜度為O(m+n)
BF算法确實實作了模式比對的目的，但同時也有較大的缺陷
假設目前有這樣一個主串S與模式串T
主串S：
模式串T：
比對過程：
顯而易見，使用BF模式比對算法，一旦遇到主串S元素與模式串T高度重合，但鮮有不同。
此種算法将進行大量重複的“主串S回退”，如此一來，時間複雜度将達到
O(m*n)
而後，D.E.Knuth與V.R.Pratt和J.H.Morris發現了一套模式比對的改進算法，根據他們的名字的字母，該算法被命名為：
KMP算法
KMP算法可以在時間複雜度為O(m+n)的時間數量級上完成模式比對操作。
其不同點在于，在比對失敗之後，不需要回溯i指針
而是利用已經“部分比對”的結果，将模式串T向右滑動盡可能遠的距離
(KMP算法比對過程1)
(KMP算法比對過程2)
(KMP算法比對過程3)
從該描述中我們提取出要使用KMP算法最核心的三個問題：1.滑動的條件 2.滑動的模式 3.滑動距離k的求解
這部分我們探究當發生“失配”後，主串S中的i應該與模式串T中的第幾個字元(這裡用K指代)繼續進行比較。
在什麼條件下我們可以将視窗進行“滑動”？或者說，怎樣才叫發生了“部分比對”？
這裡給出嚴蔚敏版的《資料結構》中，對于“部分比對”條件的定義(模式串為p，主串為s)：
①
\[p_1p_2...p_{k-1} = s_{i-k+1}s_{i-k+2}...s_{i-1}\]
②
\[p_{j-k+1}p_{j-k+2}...p_{j-1} = s_{i-k+1}s_{i-k+2}...s_{i-1}\]
③
\[p_1p_2...p_{k-1} = p_{j-k+1}p_{j-k+2}...p_{j-1} \]
剛看到這三個公式的時候，有點懵，但仔細比對之後可以發現
公式①說明：模式串p從頭開始的子串與後面某段已發生“部分比對”的主串s的子串q相同
公式②說明：模式串p在除開頭以外，有一段子串與剛才的子串q發生了“部分比對”
公式③說明：如果滿足上述兩個條件，則可以得出模式串p中有兩端相同的子串
如果滿足以上三個條件(滿足前兩個條件則第三個必定滿足),則可以快速“滑動k個位置”來進行KMP模式比對
明确了前提條件之後，我們建立應該next[j]來儲存每次比對結束後的K值
約定：
<col>
next[j]
條件
結果
當j等于1
将i向後移動一位
k
取Kmax，1<k<j 且 滿足條件③
将模式串的第k位與目前i對齊
1
其他情況
将模式串的第1位與目前i對齊
反映成代碼形式：
由
可知next[j]僅與模式串有關而與主串無關
這裡是整個KMP算法的核心部分，在我反反複複看幾十遍嚴蔚敏版的《資料結構》之後，我終于理清了整個求解滑動距離的方法。
整個算法分為兩個情況：
\[p_k = p_j \]
以及
\[p_k ≠ p_j \]
若滿足第一種情況，有
next[j+1] = next[j] + 1;
若滿足第二種情況，則又分為兩種情況
設K' = next[k],當P[K'] = P[j] 時，有
next[j+1] = next[k] + 1;
如果一直移動K'到j = 1時，還不能找到對應的P[K'] = P[j],那麼直接有
next[j+1] = 1;
在展開講求next[j]的算法之前，必須要明确的一點是：
k，j，k'，j+1分别代表串中的哪些位置
在這裡給出明确定義：
j+1就是你需要求k值的模式串位置
j就是目前需要求出K值的字元的前一個字元
k-1就是“已比對”的字首的最後一個字元
k就是“已比對”的字首的最後一個字元的後一個字元
注意
字首一定要包含第1個字元
字尾一定要包含希望求得K的字元的前一個字元
如圖所示，如果我們要求得串中第5個字元的K值，假設前四個字元K值均已經求得，設我們的目标字元指針為j+1
又有第1個‘a’與第3個‘a'比對，是以他們分别為k-1和j-1
是以第2個字元為k，第4個字元為j。
重點來了
<code>讓我們抛出一個例子，來了解next[j]的求法</code>
假設我們已知j=1，2，3，4的next[j]值分别為：0，1，1，2
由于k-1和j-1已經”比對“，則滿足前置比對條件，我們來比較pk和pj的内容，
pk = b，pj = a；
可見它們并不相等，是以k指向的b會甩鍋給“next[k]”字元，而next[k] = 1，也就是串的第一個字元‘a'
第一個字元‘a'成功與第j個字元‘a'相比對，是以依照我們定義的的pk ≠ pj的第一種情況可以得到
next[j+1] = next[k] + 1 = 2;
由此，我們可以通過之前定義的方式來确定所有的next[j]的值，下面給出串'abaabcac'的所有next[j]的值：
希望讀者能拿起筆，從next[2]開始，計算到next[8]
相信計算完上表格的讀者，已經對next[j]的計算方法有了更加深刻的了解
在這裡我也分享出自己總結的口訣：
k，j相等，直接加1
k，j不等，層層甩鍋
甩鍋失敗，直接賦1
甩鍋成功，老闆加1
釋義：
pk = pj：next[j+1] = next[j] + 1;
pk ≠ pj: 甩鍋
p[k'] = pj:next[j+1] = next[k] + 1;
p[k'] ≠ pj:next[j+1] = 1 or 繼續向next[k']甩鍋。
接下來給出代碼實作求next[j]：
通過分析代碼我們可以發現，當模式串元素有多個重複元素：
他們的next[j]為：0，1，2，3，4
是以在比對時将出現i不動，j從調用next[j]3次的情況，
在這種情況下，我們可以讓j=1，2，3，4隻進行一次比對就使得i向後移動一位（也就是next[j] = 0)
改進算法如下：
改進之後next[j] = 0,0,0,0,4,成功避免了重複比對