作者 | 小灰
來源 | 程式設計師小灰（ID：chengxuyuanxiaohui）
————— 第二天 —————
————————————
前情回顧
在字符串匹配算法的前兩講，我們分別介紹了暴力算法BF算法，利用哈希值進行比較的RK算法，以及儘量減少比較次數的BM算法，沒看過的小夥伴可以點擊下方連結：
1. BF算法和RK算法
2. BM算法
如果沒時間細看也沒關係，就讓我帶著大家簡單梳理一下。
首先，給定 「主串」 和 「模式串」 如下：
BF算法是如何工作的？
正如同它的全稱BruteForce一樣，BF算法使用簡單粗暴的方式，對主串和模式串進行逐個字符的比較：
第一輪，模式串和主串的第一個等長子串比較，發現第0位字符一致，第1位字符一致，第2位字符不一致：
第二輪，模式串向後挪動一位，和主串的第二個等長子串比較，發現第0位字符不一致：
第三輪，模式串繼續向後挪動一位，和主串的第三個等長子串比較，發現第0位字符不一致：
以此類推，一直到第N輪：
當模式串挪動到某個合適位置，逐個字符比較，發現每一位字符都是匹配時，比較結束：
BF算法的缺點很明顯，效率實在太低了，每一輪只能老老實實地把模式串右移一位，實際上做了很多無謂的比較。
而BM算法解決了這一問題。它藉助「壞字符規則」和「好後綴規則」，在每一輪比較時，讓模式串儘可能多移動幾位，減少無謂的比較。
利用BM算法，上面的主串和模式串匹配只需要比較三輪：
KMP算法的整體思路
KMP算法的整體思路是什麼樣子呢？讓我們來看一組例子：
KMP算法和BF算法的「開局」是一樣的，同樣是把主串和模式串的首位對齊，從左到右對逐個字符進行比較。
第一輪，模式串和主串的第一個等長子串比較，發現前5個字符都是匹配的，第6個字符不匹配，是一個「壞字符」：
這時候，如何有效利用已匹配的前綴 「GTGTG」 呢？
我們可以發現，在前綴「GTGTG」當中，後三個字符「GTG」和前三位字符「GTG」是相同的：
在下一輪的比較時，只有把這兩個相同的片段對齊，才有可能出現匹配。這兩個字符串片段，分別叫做最長可匹配後綴子串和最長可匹配前綴子串。
第二輪，我們直接把模式串向後移動兩位，讓兩個「GTG」對齊，繼續從剛才主串的壞字符A開始進行比較：
顯然，主串的字符A仍然是壞字符，這時候的匹配前綴縮短成了GTG：
按照第一輪的思路，我們來重新確定最長可匹配後綴子串和最長可匹配前綴子串：
第三輪，我們再次把模式串向後移動兩位，讓兩個「G」對齊，繼續從剛才主串的壞字符A開始進行比較：
以上就是KMP算法的整體思路：在已匹配的前綴當中尋找到最長可匹配後綴子串和最長可匹配前綴子串，在下一輪直接把兩者對齊，從而實現模式串的快速移動。
next 數組
next數組到底是個什麼鬼呢？這是一個一維整型數組，數組的下標代表了「已匹配前綴的下一個位置」，元素的值則是「最長可匹配前綴子串的下一個位置」。
或許這樣的描述有些晦澀，我們來看一下圖：
當模式串的第一個字符就和主串不匹配時，並不存在已匹配前綴子串，更不存在最長可匹配前綴子串。這種情況對應的next數組下標是0，next[0]的元素值也是0。
如果已匹配前綴是G、GT、GTGTGC，並不存在最長可匹配前綴子串，所以對應的next數組元素值（next[1]，next[2]，next[6]）同樣是0。
GTG的最長可匹配前綴是G，對應數組中的next[3]，元素值是1。
以此類推，
GTGT 對應 next[4]，元素值是2。
GTGTG 對應 next[5]，元素值是3。
有了next數組，我們就可以通過已匹配前綴的下一個位置（壞字符位置），快速尋找到最長可匹配前綴的下一個位置，然後把這兩個位置對齊。
比如下面的場景，我們通過壞字符下標5，可以找到next[5]=3，即最長可匹配前綴的下一個位置：
說完了next數組是什麼，接下來我們再來思考一下，如何事先生成這個next數組呢？
由於已匹配前綴數組在主串和模式串當中是相同的，所以我們僅僅依據模式串，就足以生成next數組。
最簡單的方法是從最長的前綴子串開始，把每一種可能情況都做一次比較。
假設模式串的長度是m，生成next數組所需的最大總比較次數是1+2+3+4+......+m-2 次。
顯然，這種方法的效率非常低，如何進行優化呢？
我們可以採用類似「動態規劃」的方法。首先next[0]和next[1]的值肯定是0，因為這時候不存在前綴子串；從next[2]開始，next數組的每一個元素都可以由上一個元素推導而來。
已知next[i]的值，如何推導出next[i+1]呢？讓我們來演示一下上述next數組的填充過程：
如圖所示，我們設置兩個變量i和j，其中i表示「已匹配前綴的下一個位置」，也就是待填充的數組下標，j表示「最長可匹配前綴子串的下一個位置」，也就是待填充的數組元素值。
當已匹配前綴不存在的時候，最長可匹配前綴子串當然也不存在，所以i=0，j=0，此時next[0] = 0。
接下來，我們讓已匹配前綴子串的長度加1：
此時的已匹配前綴是G，由於只有一個字符，同樣不存在最長可匹配前綴子串，所以i=1，j=0，next[1] = 0。
接下來，我們讓已匹配前綴子串的長度繼續加1：
此時的已匹配前綴是GT，我們需要開始做判斷了：由於模式串當中 pattern[j] != pattern[i-1]，即G！=T，最長可匹配前綴子串仍然不存在。
所以當i=2時，j仍然是0，next[2] = 0。
接下來，我們讓已匹配前綴子串的長度繼續加1：
此時的已匹配前綴是GTG，由於模式串當中 pattern[j] = pattern[i-1]，即G=G，最長可匹配前綴子串出現了，是G。
所以當i=3時，j=1，next[3] = next[2]+1 = 1。
接下來，我們讓已匹配前綴子串的長度繼續加1：
此時的已匹配前綴是GTGT，由於模式串當中 pattern[j] = pattern[i-1]，即T=T，最長可匹配前綴子串又增加了一位，是GT。
所以當i=4時，j=2，next[4] = next[3]+1 = 2。
接下來，我們讓已匹配前綴子串的長度繼續加1：
此時的已匹配前綴是GTGTG，由於模式串當中 pattern[j] = pattern[i-1]，即G=G，最長可匹配前綴子串又增加了一位，是GTG。
所以當i=5時，j=3，next[5] = next[4]+1 = 3。
接下來，我們讓已匹配前綴子串的長度繼續加1：
此時的已匹配前綴是GTGTGC，這時候需要注意了，模式串當中 pattern[j] ！= pattern[i-1]，即T != C，這時候該怎麼辦呢？
這時候，我們已經無法從next[5]的值來推導出next[6]，而字符C的前面又有兩段重複的子串「GTG」。那麼，我們能不能把問題轉化一下？
或許聽起來有些繞：我們可以把計算「GTGTGC」最長可匹配前綴子串的問題，轉化成計算「GTGC」最長可匹配前綴子串的問題。
這樣的問題轉化，也就相當於把變量j回溯到了next[j]，也就是j=1的局面（i值不變）：
回溯後，情況仍然是 pattern[j] ！= pattern[i-1]，即T！=C。那麼我們可以把問題繼續進行轉化：
問題再次的轉化，相當於再一次把變量j回溯到了next[j]，也就是j=0的局面：
回溯後，情況仍然是 pattern[j] ！= pattern[i-1]，即G！=C。j已經不能再次回溯了，所以我們得出結論：i=6時，j=0，next[6] = 0。
以上就是next數組元素的推導過程。
1. 對模式串預處理，生成next數組
2. 進入主循環，遍歷主串
2.1. 比較主串和模式串的字符
2.2. 如果發現壞字符，查詢next數組，得到匹配前綴所對應的最長可匹配前綴子串，移動模式串到對應位置
2.3.如果當前字符匹配，繼續循環
KMP算法的具體實現
// KMP算法主體邏輯。str是主串，pattern是模式串publicstaticintkmp(String str, String pattern) {//預處理，生成next數組int[] next = getNexts(pattern);int j = 0;//主循環，遍歷主串字符for (int i = 0; i < str.length(); i++) {while (j > 0 && str.charAt(i) != pattern.charAt(j)) {//遇到壞字符時，查詢next數組並改變模式串的起點 j = next[j];}if (str.charAt(i) == pattern.charAt(j)) { j++;}if (j == pattern.length()) {//匹配成功，返回下標return i - pattern.length() + 1;}}return-1;}// 生成Next數組privatestaticint[] getNexts(String pattern) {int[] next = newint[pattern.length()];int j = 0;for (int i=2; i<pattern.length(); i++) {while (j != 0 && pattern.charAt(j) != pattern.charAt(i-1)) {//從next[i+1]的求解回溯到 next[j] j = next[j];}if (pattern.charAt(j) == pattern.charAt(i-1)) { j++;}next[i] = j;}return next;}publicstaticvoidmain(String[] args) {String str = "ATGTGAGCTGGTGTGTGCFAA";String pattern = "GTGTGCF";int index = kmp(str, pattern);System.out.println("首次出現位置：" + index);}
【End】
阿里大牛：華先勝、丁險峰直播分享！
今晚7點，阿里巴巴集團副總裁華先勝——《人工智慧：是風、是雲，還是雨？》
面向開發者詳解視覺智能技術規模化落地的挑戰；面向企業詳述如何通過核心AI技術、產品化 及平臺化實現客戶價值並構建壁壘？