大家好，前面的有一篇文章講了子序列和全排列問題，今天我們再來看一個比較有難度的問題，那就是大名鼎鼎的KMP演算法，

本期文章原始碼：GitHub原始碼

簡介

KMP演算法是一種改進的字串匹配演算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人們稱它為克努特—莫里斯—普拉特操作（簡稱KMP演算法），KMP演算法的核心是利用匹配失敗后的資訊，盡量減少模式串與主串的匹配次數以達到快速匹配的目的，具體實作就是通過一個next()函式實作，函式本身包含了模式串的區域匹配資訊，KMP演算法的時間復雜度O(m+n) ，

說的簡單的一點，就是一個用于在主串中，查找子串的演算法，

暴力解法（BF）

在講解KMP演算法之前，我們得先理解暴力解法，因為KMP演算法就是在暴力解法的基礎之上，進行了優化，使之匹配速度加快，

人如其名，暴力解法，就是一種很暴力的解決方法，比如：主串“abbabbec”，待查找的子串為“abbec”， 請問主串中是否包含這個子串？

我們肉眼，能夠很輕松的看到從第4個字符開始，一直到末尾這一段，就是需要查找的子串，那么編譯器是如何進行查找呢？它就只能一個字符一個字符的嘗試：

上圖就是暴力解法的全部程序，通過匹配一個個字符，如果當前字符匹配成功，i和j就同時走一步；如果當前字符匹配不成功，i 就應該回到當前開始的第一個字符的下一個字符：比如圖中步驟4和步驟5，就是說的這個意思，當前是從第一個字符a開始匹配的，此時匹配失敗了，i就應該回到a字符的下一個字符，j就從0下標開始，繼續往下匹配；

當i或者j走到了字串的末尾，我們就結束回圈，然后判斷j是不是遍歷完了待查找的子串，如果確實是走到了子串的末尾，說明查找成功了，就回傳子串在主串的起始位置（i - j， 在上圖就是回傳3），反之就是：主串的字符都遍歷完了，子串的還沒遍歷完，那就是主串沒有這個子串的情況，此時回傳-1即可，

//BF演算法
//s 為主串
//m 為待查找的子串
public int BF(String s, String m) {
    if(s == null || m == null) {
        return -1;
    }
    
    char[] str1 = s.toCharArray(); //主串
    char[] str2 = m.toCharArray(); //子串
    int i = 0; //指向主串的下標
    int j = 0; //指向子串的下標
    
    //i和j的值，都還沒到末尾，回圈繼續
    while (i < str1.length && j < str2.length) {
        if (str1[i] == str2[j]) { //當前字符匹配成功
            i++;
            j++;
        } else { //當前字符匹配不成功
            i = i - j + 1; //回到開頭的下一個字符
            j = 0; //子串從頭開始
        }
    }
    
    //判斷是否遍歷完了子串，并回傳相應的值
    return j == str2.length? i - j : -1; 
}

時間復雜度：

假設主串的長度為N， 子串的長度為M，最差的情況，就如上圖的情況，只有在最后一個字符才查找成功，所以子串要從每一個字符作為起始位置開始匹配，每一個字符作為起始，都會匹配子串的長度M次，也就是說暴力解法的時間復雜度為O(N*M)，

KMP演算法

KMP演算法和BF演算法，在代碼上差別不大，在BF的代碼基礎之上，需要計算一個next陣列，在while回圈里面再加一個判斷陳述句即可，其他的代碼都是不變的，

雖然代碼改動不是很大，但是從邏輯思維上，卻是一個質的飛越，所以我們先來看一下KMP的核心：next陣列，

next陣列究竟是什么？我相信很多同學都會有這樣一個疑問，

其實next陣列，計算的待查找的子串的每個字符（不包括當前字符）前面的所有字符中，前綴字串和后綴字串相等的，并且最長的字符個數，比如：

舉一個完整的例子吧，比如子串是str2 = “ababab”，計算這個字串的next陣列如下：

首先就是從頭開始遍歷字串：（建議拿出筆和紙，一起畫一畫，更容易理解）

• j = 0; str2[j] = a

  a字符前面沒有任何字符，人為規定第一個字符的next值為-1，

• j = 1; str2[j] = b

  b字符前面只有一個字符a，有人就會說，那么next就是1咯？ 當然不是，我們還忽略了一個重要條件：計算的當前字符前面的所有字符，進行劃分前綴和后綴字串，但是所謂的前綴和后綴字串，并不包括了這前面的整體字串，說的簡單一點就是：假設b字符前面的所有字符是“abc”， 前綴字串是“abc”， 后綴字串是“abc”，這種情況是不算在內的，用數學公式解釋：前綴字串 = 后綴字串 = b字符前面所有字符，這種情況不算數，

  所以當前這個b字符，前面就只有一個字符，所以人為規定第二個字符的next值為0，

• j = 2； str2[j] = a

  a字符前面有字串“ab”， 前綴和后綴字串，排除“ab” = “ab”的情況，就沒有能夠匹配前綴和后綴的字串，所以第三個字符的next值為0，

• j = 3; str2[j] = b

  b字符前面的字串是“aba”，此時排除“aba” = ”aba“的情況， 那就只剩下前綴字串“a” = 后綴字串“a”的情況，所以第四個字符的next值為1，

• j = 4; str2[j] = a

  a字符前面的字串是“abab”，排除“abab” = “abab”的情況后，就只剩下前綴字串“ab” = 后綴字串“ab”的情況，所以第五個字符的next值為2，

• j = 5；str2[j] = b

  b字符前面的字串是“ababa”， 排除“ababa” = “ababa”的情況后，就只剩下前綴字串“aba” = 后綴字串“aba”，所以第六個字符的next值為3，

• j = 6； str2[j] = ‘\0’

  遍歷結束

所以上面例子的next陣列的值，如下圖：

那么就有同學會納悶了，在邏輯層面上，我知道該怎么計算next陣列了，但是在代碼層面上，似乎并沒有什么思路，不急，我們現在就說一下代碼怎么實作這個邏輯，

我們以上圖的最后一個字符b為例，在求解b字符所對應的next值時，b字符前面的字符，是已經計算好了next值的，所以我們需要借助b字符前面已經計算好的next值，來計算b字符的next值，

所以next陣列的計算代碼，如下：

public int[] getNextArr(String m) {
    if (m.length() < 2) { //只有一個字符
        return new int[] {-1};
    }
    if (m.length() < 3) { //只有兩個字符
        return new int[] {-1, 0};
    }
    
    char[] str = m.toCharArray();
    int[] next = new int[m.length()];
    next[0] = -1;
    next[1] = 0; //人為規定的兩個位置的next值
    int cn = 0; //表示往前跳的下標，也就是前綴字串的下一個字符，初始化就是第一個字符
    int i = 2; //從第三個字符開始判斷
    
    while (i < m.length()) {
        if (str[i - 1] == str[cn]) { 
            //當前字符的前一個字符，與cn所對應的字符比較
            next[i++] = ++cn; //等價于：next[i++] = next[i - 1] + 1; cn++; 
        } else if (cn > 0) {
            //說明當前字符沒匹配成功，cn要往前跳，找上一組前綴、后綴字串
            cn = next[cn];
        } else {
            //cn一直往前跳，都沒能與當前字符匹配成功，則當前位置next值就是0
            next[i++] = 0;
        }
    }
    
    return next; //回傳next陣列
}

next陣列的計算代碼，我們就講完了，再加把勁，就還剩最后的一點點了，

我們先來將大致的框架寫出來：

//KMP演算法
// s 為主串
// m 為待查找的子串
public int KMP(String s, String m) {
    if (s == null || m == null || s.length() < 1 || m.length() < 1) {
        return -1;
    }
    
    int[] next = getNextArr(m); //計算子串的next陣列
    
    char[] str1 = s.toCharArray();
    char[] str2 = m.toCharArray();
    int i = 0; //指向主串的下標
    int j = 0; //指向子串的下標
    
    while (i < str1.length && j < str2.length) {
        if (str1[i] == str2[j]) { //字符相等的情況，i和j同時加1
            i++;
            j++;
        } else if (j == 0) {
            
        } else {
            
        }
    }
    
    return j == str2.length? i - j : -1; //判斷子串是否遍歷完了
}

現在就還剩下while回圈里面，20行~24行的代碼，還沒填寫，

20行~24行的代碼，是在上面的if陳述句沒有為真，才會走到20行后面代碼，也就是說此時當前的字符已經沒有匹配成功了，此時就需要對j或者i進行調整，

那么對于j來說，就分為兩個情況：

1. j ！= 0時，則說明j還能往前面跳，即就是說j位置前面的字符，還有可能會有前綴、后置字串，那么j繼續往前跳即可，j = next[j]，（找j位置前面的前綴字串）
2. j == 0時，則說明j前面已經沒有字符了，換個角度說，對于當前i位置的字符，在子串中j已經走到了第一個字符，都還沒匹配成功，則說明，當前i位置的字符肯定不會匹配成功的，那么i往后走一個字符的位置，然后再回圈就進行判斷，

完整的代碼：

//KMP演算法
// s 為主串
// m 為待查找的子串
public int KMP(String s, String m) {
    if (s == null || m == null || s.length() < 1 || m.length() < 1) {
        return -1;
    }
    
    int[] next = getNextArr(m); //計算子串的next陣列
    
    char[] str1 = s.toCharArray();
    char[] str2 = m.toCharArray();
    int i = 0; //指向主串的下標
    int j = 0; //指向子串的下標
    
    while (i < str1.length && j < str2.length) {
        if (str1[i] == str2[j]) { //字符相等的情況，i和j同時加1
            i++;
            j++;
        } else if (j == 0) { //j不能再往前走了，那么i就往后走一個位置
            i++;
        } else { //j還能往前跳，尋找前面的前綴字串
            j = next[j];
        }
    }
    
    return j == str2.length? i - j : -1; //判斷子串是否遍歷完了
}

只要理解了next陣列是如何進行計算的，那么KMP演算法的就理解了一大半了，

后面的整體的代碼框架，跟BF演算法是差不多的，只需分為i和j兩個值的調整，即可！

具體的，大家可以再分別舉幾個例子，自己手動去走一遍代碼，這里就能更好的理解KMP演算法的思路，也可以看一下左程云老師所寫的《程式員代碼面試指南》一書，也有相應的講解，

好啦，本期更新就到此結束啦，我們下期見！！！