摘要：字符串的普通模式匹配普通模式匹配的原理不進(jìn)行說(shuō)明了，簡(jiǎn)單來(lái)說(shuō)就是兩個(gè)字符串的每個(gè)字符依次進(jìn)行匹配。

這篇文章主要是介紹KMP模式匹配算法，在正式介紹KMP之前我們先看一下普通模式匹配，由普通模式匹配在進(jìn)一步的推導(dǎo)KMP模式會(huì)更容易理解。

普通模式匹配的原理不進(jìn)行說(shuō)明了，簡(jiǎn)單來(lái)說(shuō)就是兩個(gè)字符串的每個(gè)字符依次進(jìn)行匹配。

public int match(String S,String T){
    int i = 0;
    int j = 0;

    while(i < S.length() && j < T.length()){
        if(S.charAt(i) == T.charAt(j)){
            i++;
            j++;
        }else{
            i = i - j + 1;
            j = 0;
        }
    }

    if(j >= T.length()){
        return i - T.length();
    }else{
        return 0;
    }
}

普通模式匹配的時(shí)間復(fù)雜度最壞的情況（即T在S的末尾）為O（(m-n+1)*n）。這種算法的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，缺點(diǎn)也顯而易見(jiàn)那就是效率較低。jdk String類內(nèi)的靜態(tài)方法indexOf底層使用的就是類似該種算法。

為了方便理解KMP模式，我們先看一下普通模式模式的流程：

栗子1：

主串：S = "abcdefgab"

子串：T = "abcdex"

觀察下普通模式匹配算法，對(duì)于要匹配的子串T = “abcdex”來(lái)說(shuō)

首字母"a"與后面的串"bcdex"中的任意一個(gè)字符都不相等;

串"bcde"與主串S的第2-5位相等，那么首字母"a"就不可能與主串S的第2-5位相等。

所以，第2 3 4 5 的判斷都是不需要的，這是個(gè)理解KMP模式的關(guān)鍵。

那么問(wèn)題來(lái)了，如果T串后面還含有首字母"a"的字符會(huì)怎么樣呢？我們?cè)诳匆粋€(gè)例子：

粟子2：

主串：S = "abcabcabc"

子串：T = “abcabx”

對(duì)于要比配的子串T = "abcabx"來(lái)說(shuō)，

T的首字母"a"與T的第2個(gè)字符"b"、第3個(gè)字符"c"均不等，且T的第1-3位字符與主串S的第1-3相等，所以，步驟2和步驟3可以省略；

T的前2位串"ab"與T的第4-5串"ab"相等，且T的第4-5串"ab"與主串S的第4-5串"ab"相等，得出T的前2位串與S的第4-5也相等，可以省略。

最后，第6步的前兩次比較也是不需要的，直接比較 主串S的第6位的"a"和子串T的第3位"c"即可，如下圖：

對(duì)比這兩個(gè)例子，可以發(fā)現(xiàn)普通模式主串S的游標(biāo)每次都是回溯到i++的位置。而經(jīng)過(guò)上面的分析后發(fā)現(xiàn)，這種回溯方式其實(shí)是不需要的，KMP模式就是解決了這些沒(méi)有必要的回溯。

既然要避免i的回溯，那么我們就要在子串T的游標(biāo)j上下工夫了。通過(guò)觀察也可發(fā)現(xiàn)，如果T的首字母與自身后面的字符有相等的情況，那j值的變化就會(huì)不相同。

例子1內(nèi)j的變化，由于首字母"a"與后面的字符都不相等，則j由6變回了1。

例子2內(nèi)j的變化，由于前綴"ab"與后面的"ab"相等，因此j從6變回了3。

有沒(méi)有看出什么規(guī)律？提示一下：

例子1內(nèi)與前綴相同的字符個(gè)數(shù)為0，j變成了1。

例子2內(nèi)與前綴相同的字符個(gè)數(shù)為2，j變成了3。

j的變化取決也當(dāng)前字符之前的串的前后綴的相似度。

根據(jù)上一節(jié)的推導(dǎo)，我們可以將T串各個(gè)位置的j的變化定義為一個(gè)數(shù)組next，next的長(zhǎng)度就是T串的長(zhǎng)度，我們可以得到下面的函數(shù)定義（為了后面讀程序方便理解，所以該函數(shù)是遵循數(shù)組下標(biāo)從0開(kāi)始的規(guī)范）：

我們來(lái)手工驗(yàn)證一下該函數(shù)。

T = "abcdex"

if j = 0, next[0] = 0;

if j = 1, "p~0~ ... p~k~" = "p~j-k~ ... p~j~" --> "a" <> "b" ,next[1] = 0;

if j = 2, 子串"abc"，也沒(méi)有重復(fù)的字符子串，next[2] = 0;

以后同理，所以最終T串的ntxt[j]為000000。

例子就列舉到這里，現(xiàn)在放下KMP的Java實(shí)現(xiàn)，其它實(shí)例大家可以使用程序進(jìn)行驗(yàn)證。

public void getNext(String T,Integer[] next){
    next[0] = 0;    //當(dāng)j = 0時(shí)，next[0] = 0

    int i = 1;
    int j = 0;
    int k = 0;
    while (i < T.length() && j < i){
        if(T.substring(0,j).equals(T.substring(i-j,i))){
            k = j;    //若有相同子串，則記錄下對(duì)應(yīng)在T串內(nèi)的位置，最終得出最長(zhǎng)匹配成功的位置
        }
        j++;

        if(j >= i){
            next[i] = k;    //若一直未匹配成功，將k = 0賦值給next[i]
            j = 1;
            k = 0;
            i++;
        }
    }
}

我們來(lái)測(cè)試 幾個(gè)字符串：

input: abcdex
output:000000

input: abcabx
output:000012

input: aaaaaaaab
output:001234567

下面是完整的KMP模式匹配算法的代碼：

package string;
public class KMPMatch {
    public void getNext(String T,Integer[] next){
        next[0] = 0;    //當(dāng)j = 0時(shí)，next[0] = 0

        int i = 1;
        int j = 0;
        int k = 0;
        while (i < T.length() && j < i){
            if(T.substring(0,j).equals(T.substring(i-j,i))){
                k = j;    //若有相同子串，則記錄下對(duì)應(yīng)在T串內(nèi)的位置，最終得出最長(zhǎng)匹配成功的位置
            }
            j++;

            if(j >= i){
                next[i] = k;    //若一直未匹配成功，將k = 0賦值給next[i]
                j = 1;
                k = 0;
                i++;
            }
        }
    }

    public int match(String S,String T){
        int i = 0;
        int j = 0;

        Integer[] next = new Integer[T.length()];
        getNext(T,next);

        while(i < S.length() && j < T.length()){
            if(j == 0 || S.charAt(i) == T.charAt(j)){
                i++;
                j++;
            }else{
                j = next[j];
            }
        }

        if(j >= T.length()){
            return i - T.length();
        }else{
            return 0;
        }
    }

    public static void main(String[] args) {
        String S = "aaaabcde";
        String T = "abcd";
        System.out.println(new KMPMatch().match(S,T));
    }
}

對(duì)于方法getNext來(lái)說(shuō)，若T的長(zhǎng)度為m，因只涉及簡(jiǎn)單的單循環(huán)，其時(shí)間復(fù)雜度為O(m)，由于i不進(jìn)行回溯，while循環(huán)的時(shí)間復(fù)雜度為O(n)。因此，整個(gè)算法的時(shí)間復(fù)雜度為O(m+n)。

對(duì)于KMP模式來(lái)說(shuō)，僅當(dāng)子串與主串之前存在許多“部分匹配”的時(shí)候才體現(xiàn)出它的優(yōu)勢(shì)，否則兩者差異并不明顯。

看下面這個(gè)例子：

S = "aaaabcde"

T = "aaaaax"

T的next分別為001234，兩個(gè)串的匹配流程如下：

從流程中可發(fā)現(xiàn)，當(dāng)中的步驟2 3 4 5都是多余的判斷。由于T串的第2 3 4 5位置的字符都與首字符相等，那么就可以用首位next[0]值去取代與它相等的字符的next[j]，下面就是對(duì)getNext方法進(jìn)行的改良，代碼如下：

public void getNextVal(String T,Integer[] nextVal){
    nextVal[0] = 0;    //當(dāng)j = 0時(shí)，next[0] = 0

    int i = 1;
    int j = 0;
    int k = 0;
    while (i < T.length() && j < i){
        if(T.substring(0,j).equals(T.substring(i-j,i))){
            k = j;    //若有相同子串，則記錄下對(duì)應(yīng)在T串內(nèi)的位置，最終得出最長(zhǎng)匹配成功的位置
        }
        j++;

        if(j >= i){
            //當(dāng)前字符與前綴字符相同中，則當(dāng)前字符j為nextVal[i]
            if(T.charAt(i) == T.charAt(k)){
                nextVal[i] = nextVal[k];
            }else {
                nextVal[i] = k;
            }
            j = 1;
            k = 0;
            i++;
        }
    }
}

學(xué)習(xí)是一個(gè)過(guò)程，對(duì)學(xué)習(xí)到的知識(shí)進(jìn)行理解、吸收、整理，并將其按自己的理解進(jìn)行輸出。

參考材料：《大話數(shù)據(jù)結(jié)構(gòu)》