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

本期文章源碼：GitHub源碼

簡介

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

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

暴力解法（BF）

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

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

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

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

當i或者j走到了字符串的末尾，我們就結(jié)束循環(huán)。然后判斷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的值，都還沒到末尾，循環(huán)繼續(xù)
    while (i < str1.length && j < str2.length) {
        if (str1[i] == str2[j]) { //當前字符匹配成功
            i++;
            j++;
        } else { //當前字符匹配不成功
            i = i - j + 1; //回到開頭的下一個字符
            j = 0; //子串從頭開始
        }
    }
    
    //判斷是否遍歷完了子串，并返回相應(yīng)的值
    return j == str2.length? i - j : -1; 
}

時間復雜度：

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

KMP算法

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

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

next數(shù)組究竟是什么？我相信很多同學都會有這樣一個疑問。

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

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

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

• j = 0; str2[j] = a

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

• j = 1; str2[j] = b

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

所以當前這個b字符，前面就只有一個字符，所以人為規(guī)定第二個字符的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'

遍歷結(jié)束

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

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

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

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

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; //人為規(guī)定的兩個位置的next值
    int cn = 0; //表示往前跳的下標。也就是前綴字符串的下一個字符。初始化就是第一個字符
    int i = 2; //從第三個字符開始判斷
    
    while (i < m.length()) {
        if (str[i - 1] == str[cn]) { 
            //當前字符的前一個字符，與cn所對應(yīng)的字符比較
            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數(shù)組
}

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

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

//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數(shù)組
    
    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; //判斷子串是否遍歷完了
}

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

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

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

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

j == 0時，則說明j前面已經(jīng)沒有字符了，換個角度說，對于當前i位置的字符，在子串中j已經(jīng)走到了第一個字符，都還沒匹配成功，則說明，當前i位置的字符肯定不會匹配成功的。那么i往后走一個字符的位置，然后再循環(huá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); //計算子串的next數(shù)組
    
    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數(shù)組是如何進行計算的，那么KMP算法的就理解了一大半了。

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

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

好啦，本期更新就到此結(jié)束啦，我們下期見?。。?/p>

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

最新評論