KMP算法詳解

KMP 算法主要用于字符串匹配的，他的時(shí)間復(fù)雜度 O(m+n) 。常規(guī)的字符串匹配我們一般都這樣做，使用兩個(gè)指針，一個(gè)指向主串，一個(gè)指向模式串，如果他倆指向的字符一樣，他倆同時(shí)往右移一步，如果他倆指向的字符不一樣，模式串的指針重新指向他的第一個(gè)字符，主串的指針指向他上次開(kāi)始匹配的下一個(gè)字符，如下圖所示。

我們看到當(dāng)模式串和主串匹配失敗的時(shí)候，模式串會(huì)從頭開(kāi)始重新匹配，主串也會(huì)回退，但我們知道失敗字符之前的子串都是匹配成功的，那么這個(gè)信息能不能被我們利用呢？當(dāng)然可以，這個(gè)就是我們這里要講的 KMP 算法，他就是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達(dá)到快速匹配的目的。

當(dāng)使用 KMP 算法的時(shí)候，如果某個(gè)字符匹配失敗，主串指針不回退，而模式串指針不一定回到他的第一個(gè)字符，如下圖所示。

當(dāng)字符 e 和 d 匹配失敗之后，主串指針不回退，模式串指針指向字符 c ，然后在繼續(xù)判斷。主串指針不回退好操作，但模式串指針怎么確定是回到字符 c ，而不是其他位置呢？這是因?yàn)樵谧址?e 匹配失敗后，字符 e 前面有 2 個(gè)字符 ab 和最開(kāi)始的 2 個(gè)字符 ab 相同，所以我們可以跳過(guò)前 2 個(gè)字符。也就是說(shuō)模式串匹配某一個(gè)字符失敗的時(shí)候，如果這個(gè)失敗的字符前面有 m 個(gè)字符和最開(kāi)始的 m 個(gè)字符相同，那么下次比較的時(shí)候就可以跳過(guò)模式串的前 m 個(gè)字符，如下圖所示。

通過(guò)上面的圖我們可以知道，當(dāng)某個(gè)字符匹配失敗的時(shí)候，他前面的肯定都是成功的，也就是說(shuō)字符串 s1 和字符串 s2 完全一樣。在模式串中，匹配失敗的字符前面 b4 和 b3 是相同的，所以我們可以得到 b1，b2，b3，b4 都是相同的，也就是說(shuō)b2 和 b3 也是相同的，既然是相同的，跳過(guò)即可，不需要在比較了，直接從他們的下一個(gè)字符開(kāi)始匹配。

KMP 算法的核心部分就是找出模式串中每個(gè)字符前面到底有多少字符和最開(kāi)始的字符相同，我們用 next 數(shù)組表示。有的描述成真前綴和真后綴的相同的數(shù)量。這里要注意當(dāng)前字符前面的字符不包含第 1 個(gè)字符，最開(kāi)始的字符也不能包含當(dāng)前字符，比如在模式串 abc 中不能說(shuō)字符 c 前面有 ab 和最開(kāi)始的 ab 相同，來(lái)看下表。

我們看到字符 e 前面有 ab 和最開(kāi)始的字符 ab 相同，長(zhǎng)度是 2 。在看第 2 個(gè) a 前面沒(méi)有（不包含自己）和最開(kāi)始字符有相同的，所以是 0 。在任何模式串的第 2 個(gè)字符前面都沒(méi)有和最開(kāi)始字符有相同的，因?yàn)榍懊娴氖遣话谝粋€(gè)字符，所以 next[1]=0 。如果第 2 個(gè)沒(méi)有，那么第 1 個(gè)就更沒(méi)有了，為了區(qū)分，可以讓 next[0]=-1 ，當(dāng)然等于 0 也可以，需要特殊處理下即可。我們先來(lái)看下 next 數(shù)組怎么求。

使用兩個(gè)指針 i 和 j ，其中 j 是字符 p[i] 前面與最開(kāi)始字符相同的數(shù)量，也是 next[i] 。如果 p[j]==p[i]，也就是說(shuō)字符 p[i+1] 前面有 j+1 個(gè)字符和最開(kāi)始的 j+1 個(gè)字符相同，所以可以得到 next[i+1]=j+1 ，這個(gè)很容易理解。如果 p[j]！=p[i]，我們讓指針 j 等于 next[j] ，然后重新和 p[i] 比較，這就是回退，這個(gè)回退也是 KMP 算法的最核心部分，我們來(lái)分析下為什么要這樣回退。

如上圖所示，如果 nxet[j] 大于 0 ，那么 j 前面的 b2 和 b1 是相同的，我們知道 S1 和 S2 也是相同的，所以我們可以得出 b1，b2，b3，b4 都是相同的，如果 p[i]!=p[j] ，只需要讓 j 回退到 next[j] ，然后 i 和 j 在重新比較，這個(gè) next[j] 就是 b1 的長(zhǎng)度，因?yàn)?b1 和 b4 是相同的，所以不需要再比較了。如果還不相同， j 繼續(xù)回退，直到回退到 -1 為止，我們拿個(gè)真實(shí)的字符串看下，如下圖所示。

我們看到 b1，b2，b3，b4 是相同的，他們都是字符串 "abc" ，如果 p[i]!=p[j] ，我們就讓 j 回退到 next[j] ，因?yàn)樗麄兦懊?b1 和 b4 是相同的，沒(méi)必須要在比較了，最后再來(lái)看下代碼。

public int strStr(String s, String p) {
    int i = 0;// 主串S的下標(biāo)。
    int j = 0;// 模式串P的下標(biāo)。
    int[] next = new int[p.length()];
    getNext(p, next);// 計(jì)算next數(shù)組。
    while (i < s.length() && j < p.length()) {
        // 如果j為-1或者p[i]==p[j]，i和j都往后移一步。當(dāng)j為-1時(shí)，
        // 說(shuō)明p[i]!=p[0]，然后i往后移一步，j也往后移一步指向p[0]。
        if (j == -1 || s.charAt(i) == p.charAt(j)) {
            i++;
            j++;
            if (j == p.length())// 匹配成功。
                return i - j;
        } else {
            // 匹配失敗，j回退，跳過(guò)模式串P前面相同的字符繼續(xù)比較。
            j = next[j];
        }
    }
    return -1;
}

private void getNext(String p, int next[]) {
    int length = p.length();
    int i = 0;
    int j = -1;
    next[0] = -1;// 默認(rèn)值。
    // 最后一個(gè)字符不需要比較。
    while (i < length - 1) {
        // 如果j為-1或者p[i]==p[j]，i和j都往后移一步。
        if (j == -1 || p.charAt(i) == p.charAt(j)) {
            i++;
            j++;
            // j是字符p[i]前面和最開(kāi)始字符相同的數(shù)量。
            next[i] = j;
        } else {
            j = next[j];// 回退，KMP的核心代碼。
        }
    }
}

KMP優(yōu)化

我們來(lái)看下表 ，當(dāng)模式串在下標(biāo)為 4 的位置匹配失敗的時(shí)候，下一步 j 會(huì)回退到下標(biāo)為 1 的位置，但這兩個(gè)位置的字符是一樣的，既然一樣，拿過(guò)來(lái)比較也是不會(huì)成功，所以如果字符一樣，我們可以優(yōu)化一下，往前查找相同的子串。

來(lái)看下代碼：

private void getNext(String p, int next[]) {
    int length = p.length();
    int i = 0;
    int j = -1;
    next[0] = -1;// 默認(rèn)值。
    // 最后一個(gè)字符不需要比較。
    while (i < length - 1) {
        // 如果j為-1或者p[i]==p[j]，i和j都往后移一步。
        if (j == -1 || p.charAt(i) == p.charAt(j)) {
            i++;
            j++;
            // 這里要注意，i和j都已經(jīng)執(zhí)行了自增操作。
            if (p.charAt(i) == p.charAt(j))
                next[i] = next[j];
            else
                next[i] = j;
        } else {
            j = next[j];// 回退，KMP的核心代碼。
        }
    }
}

如果前面查找的還是相同的，我們?cè)撛趺崔k呢？是不是需要寫個(gè)遞歸，繼續(xù)往前找？實(shí)際上是不需要的，比如模式串 "aaaaaaaaaab" ，如果沒(méi)優(yōu)化他是這樣的。

如果優(yōu)化之后，當(dāng)最后一個(gè) a 匹配不成功的時(shí)候，他會(huì)回退到前面一個(gè) a ，實(shí)際上前一個(gè) a 在計(jì)算的時(shí)候已經(jīng)回退過(guò)了，就是 -1 ，所以不需要遞歸，直接賦值就行。