概述

KMP是字符串匹配的經(jīng)典算法。其中包含的思想，是非常有趣的。本文作為KMP算法的介紹和備忘錄。

場景

KMP算法要解決的問題就是在字符串（也叫主串）中的模式（pattern）定位問題。說簡單點就是我們平時常說的關(guān)鍵字搜索。模式串就是關(guān)鍵字（接下來稱它為P），如果它在一個主串（接下來稱為T）中出現(xiàn)，就返回它的具體位置，否則返回-1（常用手段）。

BF算法

BF算法，即暴風(fēng)(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是將目標(biāo)串S的第一個字符與模式串T的第一個字符進(jìn)行匹配，若相等，則繼續(xù)比較S的第二個字符和 T的第二個字符；若不相等，則比較S的第二個字符和T的第一個字符，依次比較下去，直到得出最后的匹配結(jié)果。BF算法是一種蠻力算法。

/**
 * 暴力破解法
 * @param ts 主串
 * @param ps 模式串
 * @return 如果找到，返回在主串中第一個字符出現(xiàn)的下標(biāo)，否則為-1
 */

public static int bf(String ts, String ps) {
    char[] t = ts.toCharArray();
    char[] p = ps.toCharArray();
    int i = 0; // 主串的位置
    int j = 0; // 模式串的位置
    while (i < t.length && j < p.length) {
       if (t[i] == p[j]) { // 當(dāng)兩個字符相同，就比較下一個
           i++;
           j++;
       } else {
           i = i - j + 1; // 一旦不匹配，i后退
           j = 0; // j歸0
       }
    }
    if (j == p.length) {
       return i - j;
    } else {
       return -1;
    }
}

BF算法的時間復(fù)雜度為：O(m*n)

這樣的方法顯然是不夠巧妙的。比如在下面的例子：

當(dāng)我們發(fā)現(xiàn)在i=j=3不匹配時，我們并不需要 i = 1 , j = 0 。我們可以從 i = 3 , j = 1開始匹配。

究其原因，是因為我們的p串(模式串)中，有兩個A。如果我們已經(jīng)成功到了j=3，就說明在t串(主串)中也有兩個A。那在j==3后面失敗之后，我們可以從t串(主串)中的第二個A開始匹配。而不用盲目地從t串的下一位開始匹配。

所以，我們可以得到，在ABAD這樣的串中，如果j==3時失敗。我們一定是i不變，j從1開始匹配。
注意，這個規(guī)則只與p串(模式串)的內(nèi)容有關(guān)，與t串(主串)的內(nèi)容無關(guān)。

所以，我們只需要將上面的BF算法，稍作修改，就可以優(yōu)化我們的時間復(fù)雜度，優(yōu)化之后的算法，就是KMP算法。

KMP

先說結(jié)論，KMP算法，其實就是將上面的BF算法的。不相等時的情況，進(jìn)行修改，將：

else {
           i = i - j + 1; // 一旦不匹配，i后退
           j = 0; // j歸0
       }

換成了

else {
          int[] next = getNext(ps);
           j = next[j]; // j回到指定位置
       }

所以接下來，我們就是要思考，getNext的原理。

public static int[] getNext(String ps) {
    char[] p = ps.toCharArray();
    int[] next = new int[p.length];
    next[0] = -1;
    int j = 0;
    int k = -1;
    while (j < p.length - 1) {
       if (k == -1 || p[j] == p[k]) {
           next[++j] = ++k;
       } else {
           k = next[k];
       }
    }
    return next;
}

這一段函數(shù)是比較難理解的。我們需要根據(jù)每一個判斷條件，循徐漸進(jìn)的思考。

if 中的條件有兩個 k == -1 || p[j] == p[k]
后面一個條件很容易理解，當(dāng)我們的串中，有兩個元素相等時，我們就可以做一些特殊的操作，就像我們上面舉的例子一樣。至于具體是做什么操作，我們先不看。

假設(shè)，我們的字符串中，沒有任何相同的元素。

那么 p[j] == p[k] 就永遠(yuǎn)不會實現(xiàn)。此時的代碼是:

    next[0] = -1;
    int j = 0;
    int k = -1;
    while (j < p.length - 1) {
       if (k == -1 ) {
           next[++j] = ++k;
       } else {
           k = next[k];
       }
    }

此時，next所有值都會為0。而k只會在0和-1之間徘徊。

我們再看回之前的循環(huán)：

public static int[] getNext(String ps) {
    char[] p = ps.toCharArray();
    int[] next = new int[p.length];
    next[0] = -1;
    int j = 0;
    int k = -1;
    while (j < p.length - 1) {
       if (k == -1 || p[j] == p[k]) {
           next[++j] = ++k;
       } else {
           k = next[k];
       }
    }
    return next;
}

當(dāng)p串中，某兩個元素相等時，那么后者的下一位，如果失敗就可以跳回到前者的下一位了。此處j是后者，k是前者。
如果兩個元素不相等時，k = next[k]，就是整個算法中最難理解的一句話。

我們知道，k是p串中，兩個比較指針的靠前者。next數(shù)組是存放，如果對比不想等時的回跳指針。所以 k = next[k]從原理上來講，是單純的指針回跳。

k只有在p[j] == p[k]時，才會一直增長，所以我們可以理解為：p[0-k]和p[j-k]這兩段是完全相等的。此時接下來如果發(fā)生不相等，k回跳到一個更小的串，進(jìn)行比較。如果比較相等，就只需要回這個小串。

舉一個特例就很容易明白了

//  a b a d a b a b e
// -1 0 0 1 0 1 2 3  

當(dāng)最后j = 6 k = 2時
next[7] = 3 , k = 3
然后因為p[7] != p[3]
k = next[3] = 1
此時因為p[1] == p[7]
所以如果 e 匹配不到時，我們依然可以從2進(jìn)行匹配，因為我們雖然不能確保a b a d a b a b 但我們至少確定了前面的串 a b 不需要再匹配了。

所以，k = next[k]是一個縮小匹配串的操作。
當(dāng)我們到第7位時，發(fā)現(xiàn) a b a d的匹配串，無法出現(xiàn)兩次時，我們的k回到第1位，去確定b。如果b與當(dāng)前相等，那a b的串還是出現(xiàn)了。

以上，KMP的時間復(fù)雜度為：O(m+n)，空間復(fù)雜度為：O(n)

總結(jié)

所以 KMP的理解和記憶，可分為三部分。BF算法、假設(shè)有g(shù)etNext的計算方式和getNext的實現(xiàn)。

其中 getNext中，最復(fù)雜的就是k = next[k]這一回跳遞歸邏輯。

有以上幾點，KMP就不那么難了。

如有問題，歡迎指正。