大家好，前面的有一篇文章講了子序列和全排列問(wèn)題，今天我們?cè)賮?lái)看一個(gè)比較有難度的問(wèn)題。那就是大名鼎鼎的KMP算法。

本期文章源碼：GitHub源碼

簡(jiǎn)介

KMP算法是一種改進(jìn)的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人們稱它為克努特—莫里斯—普拉特操作（簡(jiǎn)稱KMP算法）。KMP算法的核心是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達(dá)到快速匹配的目的。具體實(shí)現(xiàn)就是通過(guò)一個(gè)next()函數(shù)實(shí)現(xiàn)，函數(shù)本身包含了模式串的局部匹配信息。KMP算法的時(shí)間復(fù)雜度O(m+n) 。

說(shuō)的簡(jiǎn)單的一點(diǎn)，就是一個(gè)用于在主串中，查找子串的算法。

暴力解法（BF）

在講解KMP算法之前，我們得先理解暴力解法，因?yàn)镵MP算法就是在暴力解法的基礎(chǔ)之上，進(jìn)行了優(yōu)化，使之匹配速度加快。

人如其名，暴力解法，就是一種很暴力的解決方法。比如：主串“abbabbec”，待查找的子串為“abbec”， 請(qǐng)問(wèn)主串中是否包含這個(gè)子串？

我們?nèi)庋?，能夠很輕松的看到從第4個(gè)字符開(kāi)始，一直到末尾這一段，就是需要查找的子串。那么編譯器是如何進(jìn)行查找呢？它就只能一個(gè)字符一個(gè)字符的嘗試：

上圖就是暴力解法的全部過(guò)程，通過(guò)匹配一個(gè)個(gè)字符，如果當(dāng)前字符匹配成功，i和j就同時(shí)走一步；如果當(dāng)前字符匹配不成功，i 就應(yīng)該回到當(dāng)前開(kāi)始的第一個(gè)字符的下一個(gè)字符：比如圖中步驟4和步驟5，就是說(shuō)的這個(gè)意思，當(dāng)前是從第一個(gè)字符a開(kāi)始匹配的，此時(shí)匹配失敗了，i就應(yīng)該回到a字符的下一個(gè)字符，j就從0下標(biāo)開(kāi)始，繼續(xù)往下匹配；

當(dāng)i或者j走到了字符串的末尾，我們就結(jié)束循環(huán)。然后判斷j是不是遍歷完了待查找的子串，如果確實(shí)是走到了子串的末尾，說(shuō)明查找成功了，就返回子串在主串的起始位置（i - j， 在上圖就是返回3），反之就是：主串的字符都遍歷完了，子串的還沒(méi)遍歷完，那就是主串沒(méi)有這個(gè)子串的情況，此時(shí)返回-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; //指向主串的下標(biāo)
    int j = 0; //指向子串的下標(biāo)
    
    //i和j的值，都還沒(méi)到末尾，循環(huán)繼續(xù)
    while (i < str1.length && j < str2.length) {
        if (str1[i] == str2[j]) { //當(dāng)前字符匹配成功
            i++;
            j++;
        } else { //當(dāng)前字符匹配不成功
            i = i - j + 1; //回到開(kāi)頭的下一個(gè)字符
            j = 0; //子串從頭開(kāi)始
        }
    }
    
    //判斷是否遍歷完了子串，并返回相應(yīng)的值
    return j == str2.length? i - j : -1; 
}

時(shí)間復(fù)雜度：

假設(shè)主串的長(zhǎng)度為N， 子串的長(zhǎng)度為M。最差的情況，就如上圖的情況，只有在最后一個(gè)字符才查找成功。所以子串要從每一個(gè)字符作為起始位置開(kāi)始匹配，每一個(gè)字符作為起始，都會(huì)匹配子串的長(zhǎng)度M次，也就是說(shuō)暴力解法的時(shí)間復(fù)雜度為O(N*M)。

KMP算法

KMP算法和BF算法，在代碼上差別不大。在BF的代碼基礎(chǔ)之上，需要計(jì)算一個(gè)next數(shù)組，在while循環(huán)里面再加一個(gè)判斷語(yǔ)句即可，其他的代碼都是不變的。

雖然代碼改動(dòng)不是很大，但是從邏輯思維上，卻是一個(gè)質(zhì)的飛越。所以我們先來(lái)看一下KMP的核心：next數(shù)組。

next數(shù)組究竟是什么？我相信很多同學(xué)都會(huì)有這樣一個(gè)疑問(wèn)。

其實(shí)next數(shù)組，計(jì)算的待查找的子串的每個(gè)字符（不包括當(dāng)前字符）前面的所有字符中，前綴字符串和后綴字符串相等的，并且最長(zhǎng)的字符個(gè)數(shù)。比如：

舉一個(gè)完整的例子吧，比如子串是str2 = “ababab”，計(jì)算這個(gè)字符串的next數(shù)組如下：

首先就是從頭開(kāi)始遍歷字符串：（建議拿出筆和紙，一起畫(huà)一畫(huà)，更容易理解）

• j = 0; str2[j] = a

a字符前面沒(méi)有任何字符，人為規(guī)定第一個(gè)字符的next值為-1。

• j = 1; str2[j] = b

b字符前面只有一個(gè)字符a，有人就會(huì)說(shuō)，那么next就是1咯？ 當(dāng)然不是，我們還忽略了一個(gè)重要條件：計(jì)算的當(dāng)前字符前面的所有字符，進(jìn)行劃分前綴和后綴字符串，但是所謂的前綴和后綴字符串，并不包括了這前面的整體字符串。說(shuō)的簡(jiǎn)單一點(diǎn)就是：假設(shè)b字符前面的所有字符是“abc”， 前綴字符串是“abc”， 后綴字符串是“abc”，這種情況是不算在內(nèi)的。用數(shù)學(xué)公式解釋：前綴字符串 = 后綴字符串 = b字符前面所有字符。這種情況不算數(shù)。

所以當(dāng)前這個(gè)b字符，前面就只有一個(gè)字符，所以人為規(guī)定第二個(gè)字符的next值為0。

• j = 2； str2[j] = a

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

• j = 3; str2[j] = b

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

• j = 4; str2[j] = a

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

• j = 5；str2[j] = b

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

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

遍歷結(jié)束

所以上面例子的next數(shù)組的值，如下圖：

那么就有同學(xué)會(huì)納悶了，在邏輯層面上，我知道該怎么計(jì)算next數(shù)組了，但是在代碼層面上，似乎并沒(méi)有什么思路。不急，我們現(xiàn)在就說(shuō)一下代碼怎么實(shí)現(xiàn)這個(gè)邏輯。

我們以上圖的最后一個(gè)字符b為例。在求解b字符所對(duì)應(yīng)的next值時(shí)，b字符前面的字符，是已經(jīng)計(jì)算好了next值的。所以我們需要借助b字符前面已經(jīng)計(jì)算好的next值，來(lái)計(jì)算b字符的next值。

所以next數(shù)組的計(jì)算代碼，如下：

public int[] getNextArr(String m) {
    if (m.length() < 2) { //只有一個(gè)字符
        return new int[] {-1};
    }
    if (m.length() < 3) { //只有兩個(gè)字符
        return new int[] {-1, 0};
    }
    
    char[] str = m.toCharArray();
    int[] next = new int[m.length()];
    next[0] = -1;
    next[1] = 0; //人為規(guī)定的兩個(gè)位置的next值
    int cn = 0; //表示往前跳的下標(biāo)。也就是前綴字符串的下一個(gè)字符。初始化就是第一個(gè)字符
    int i = 2; //從第三個(gè)字符開(kāi)始判斷
    
    while (i < m.length()) {
        if (str[i - 1] == str[cn]) { 
            //當(dāng)前字符的前一個(gè)字符，與cn所對(duì)應(yīng)的字符比較
            next[i++] = ++cn; //等價(jià)于：next[i++] = next[i - 1] + 1; cn++; 
        } else if (cn > 0) {
            //說(shuō)明當(dāng)前字符沒(méi)匹配成功，cn要往前跳，找上一組前綴、后綴字符串
            cn = next[cn];
        } else {
            //cn一直往前跳，都沒(méi)能與當(dāng)前字符匹配成功，則當(dāng)前位置next值就是0
            next[i++] = 0;
        }
    }
    
    return next; //返回next數(shù)組
}

next數(shù)組的計(jì)算代碼，我們就講完了，再加把勁，就還剩最后的一點(diǎn)點(diǎn)了。

我們先來(lái)將大致的框架寫(xiě)出來(lá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); //計(jì)算子串的next數(shù)組
    
    char[] str1 = s.toCharArray();
    char[] str2 = m.toCharArray();
    int i = 0; //指向主串的下標(biāo)
    int j = 0; //指向子串的下標(biāo)
    
    while (i < str1.length && j < str2.length) {
        if (str1[i] == str2[j]) { //字符相等的情況，i和j同時(shí)加1
            i++;
            j++;
        } else if (j == 0) {
            
        } else {
            
        }
    }
    
    return j == str2.length? i - j : -1; //判斷子串是否遍歷完了
}

現(xiàn)在就還剩下while循環(huán)里面，20行~24行的代碼，還沒(méi)填寫(xiě)。

20行~24行的代碼，是在上面的if語(yǔ)句沒(méi)有為真，才會(huì)走到20行后面代碼。也就是說(shuō)此時(shí)當(dāng)前的字符已經(jīng)沒(méi)有匹配成功了。此時(shí)就需要對(duì)j或者i進(jìn)行調(diào)整。

那么對(duì)于j來(lái)說(shuō)，就分為兩個(gè)情況：

j ！= 0時(shí)，則說(shuō)明j還能往前面跳，即就是說(shuō)j位置前面的字符，還有可能會(huì)有前綴、后置字符串。那么j繼續(xù)往前跳即可。j = next[j]。（找j位置前面的前綴字符串）

j == 0時(shí)，則說(shuō)明j前面已經(jīng)沒(méi)有字符了，換個(gè)角度說(shuō)，對(duì)于當(dāng)前i位置的字符，在子串中j已經(jīng)走到了第一個(gè)字符，都還沒(méi)匹配成功，則說(shuō)明，當(dāng)前i位置的字符肯定不會(huì)匹配成功的。那么i往后走一個(gè)字符的位置，然后再循環(huán)就進(jìn)行判斷。

完整的代碼：

//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); //計(jì)算子串的next數(shù)組
    
    char[] str1 = s.toCharArray();
    char[] str2 = m.toCharArray();
    int i = 0; //指向主串的下標(biāo)
    int j = 0; //指向子串的下標(biāo)
    
    while (i < str1.length && j < str2.length) {
        if (str1[i] == str2[j]) { //字符相等的情況，i和j同時(shí)加1
            i++;
            j++;
        } else if (j == 0) { //j不能再往前走了，那么i就往后走一個(gè)位置
            i++;
        } else { //j還能往前跳，尋找前面的前綴字符串
            j = next[j];
        }
    }
    
    return j == str2.length? i - j : -1; //判斷子串是否遍歷完了
}

只要理解了next數(shù)組是如何進(jìn)行計(jì)算的，那么KMP算法的就理解了一大半了。

后面的整體的代碼框架，跟BF算法是差不多的。只需分為i和j兩個(gè)值的調(diào)整，即可！

具體的，大家可以再分別舉幾個(gè)例子，自己手動(dòng)去走一遍代碼，這里就能更好的理解KMP算法的思路。也可以看一下左程云老師所寫(xiě)的《程序員代碼面試指南》一書(shū)，也有相應(yīng)的講解。

好啦，本期更新就到此結(jié)束啦，我們下期見(jiàn)?。?！

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)徹底理解關(guān)于KMP算法的文章就介紹到這了,更多相關(guān)Java KMP內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！