KMP算法記錄

以" abcde "為例子

1、字首字元串

字首字元串，即 a、ab、abc、abcd、abcde

其中最長字首字元串為 abcde

2、字尾字元串

e、de、cde、bcde、abcde

最長字尾字元串為 abcde

提前約定：主串用 mainStr 表示，子串用 patternStr 表示

這裡mainStrin假設為" aaaaaaaaab "，patternStr設為" aaaab "

1、最初的算法：BF算法 暴力搜尋

所謂暴力搜尋，就是從主串mainStr與子串patternStr一個一個比對，不滿足重新來

暴力搜尋會出現“回溯”問題

<code>{ for(int i=0;i&lt;mainStrLen;i++){ //主串mainStr周遊 for(int j=0;j&lt;patternStrLen;j++){ //子串patternStr周遊 /** * 主串從 i 的位置，同子串一同向後移動挨個比較 * 如果有一個不相同，則跳出：言外之意就是，主串從 i+j 的地方回溯到原來 i 的位置 * 之後 i++ 向後移動一格，重新繼續挨個比較 （是以意味着，上一回合 i+j 挨個比較的 * 時候，主串 i++ 的位置已經被比較過了，甚至後面的也被比較過了，現在又要從i++的位置 * 重新挨個比較，這就是無用功的地方） */ if(mainStr.charAt(i+j)!=patternStr.charAt(j)) break; /** * 如果比對完了patternStr子串，說明比對成功 */ if(j==patternStrLen-1) return i; } } return -1; }</code>

2、KMP算法要解決BF算法中的點

解決BF算法指針回溯問題

解決辦法：利用patternStr目前比對位置之前的字元串的不包含自身的 最長字首字元串 與 最長字尾字元串 相同的情況，跳過 最長字首字元串 位置，來到它的後一個位置位置，直接去比對不相同的部分（這個部分詳情看頂部哔哩哔哩連接配接，有動畫講解）

例如 主串為ABxxxABCxxxxxx，子串為ABxxxABE，當比對到主串字元 C 和子串最後一個字元 E 的位置時，這裡說的“patternStr目前比對位置之前的字元串”表示為E之前的“ABxxxAB”，它的不包含自身的 最長字首字元串 為 AB ，最長字尾字元串為後面的 AB，是以當E這個位置與C不相同時，下一次比較就隻需要從主串目前比對位置 C ,繼續和子串剛剛的 最長字首字元串AB 之後的位置開始比較（就是AB之後的xxx的第一個，這裡稱為跳轉位置，即最長字首長度+1），這樣主串不需要回溯，子串也不需要從頭開始挨個對比。而這裡有一個點就是，憑什麼主串不回溯，ABxxxABC之間的xxx可以跳過？萬一他們恰好滿足整個字元串比對怎麼辦。這個還是可以看那個哔哩哔哩視訊裡的講解。隻要保證 最長字首字元串 與 最長字尾字元串 确确實實是剛剛那兩個 AB，那麼他們就一定可以跳過，因為如果xxx中有滿足比對的情況，則剛剛說的AB就不可能是最長字首字元串與最長字尾字元串。

得到結論：

引導出Next數組：是以通過上面，可以得到一個結論：子串每一個位置都可以有一個跳轉位置，使得這個位置不比對時，可以調到某個位置繼續與主串位置繼續比對（包括回到子串開頭位置），是以可以把這些跳轉位置寫成數組，與子串每一個字元一一對應，這個數組就是 Next 數組。每一次遇到不比對時，就通過這個數組來獲得下一個比較位置。

Next數組和主串其實沒有任何關系，任何子串一旦固定，那麼其對應的Next數組就固定了。因為是最長字首字元串和最長字尾字元串隻取決于子串（其實很好了解，仔細想想，為什麼要弄這兩個前字尾字元串來做參考，就是因為他倆一個是字元串開頭，一個是字元串末尾，并且相等，是以子串就不需要回到開頭了，隻需要到跳轉位置就好了）。

如何求解 Next數組？吐槽一句，其實在子串裡找最長字首字元串和其對應的最長字尾字元串，本身就是一個比對，這個算法真反人類

求解過程：參考頂部的第二個網址

看遠一些，你就不會被困難絆倒