一：什么是KMP算法祈匙？

KMP誕生背景：

KMP(Knuth-Morris-Pratt)三位大佬聯(lián)名提出锌蓄，故以他們姓名的首字母命名安岂，不得不說驾荣，他們的貢獻巨大外构，因為在計算機的世界，子串模式匹配的場景非常多秘车，越是底層的地方典勇，其運行的性能越是重要劫哼。在KMP算法問世之前叮趴，其實在子串匹配上采用的都是暴力匹配，我們一般稱之為樸素算法权烧，可能是因為算法比較容易想到吧眯亦，所以很樸素伤溉。

樸素匹配算法：

假設稱主串為str，模式串為ptr妻率，如果采用暴力匹配乱顾，那其實就是將str和ptr逐個字符進行比較，如果匹配失敗了宫静，就將str后移一個位置走净，然后在進行逐一比較，考慮一下最差情況的時間復雜度達到了(str.length-ptr.length)*ptr.length孤里。顯然這是一種較差的算法伏伯。

樸素匹配算法.png

下面給出一下實現(xiàn)代碼吧，就當為KMP算法預預熱：

public class NaiveMatchingString {
    /**
     * 字符串匹配算法捌袜，簡單易理解的就是暴力匹配说搅，但是時間復雜度較高
     */
    /**
     *
     * @param str:主串
     * @param ptr:用于匹配的模式串
     * @return  返回的是ptr匹配上str的時候，str的第一個字符所在字符串的位置虏等，如果匹配不上
     * 則返回0
     */
    public int NaiveMatch(String str,String ptr){
        int str_index = 0;// 表示匹配str所在的腳標
        int str_move_index; // 表示匹配ptr過程中移動的腳標
        int ptr_index;// 表示匹配ptr所在的腳標
        for (str_move_index = str_index;str_index<=str.length()-ptr.length();str_index++,str_move_index++){
            for (ptr_index = 0;str.charAt(str_move_index) == ptr.charAt(ptr_index);ptr_index++,str_move_index++){
                if (ptr_index == ptr.length()-1){return str_index;}
            }
            str_move_index = str_index;
        }
        return 0;
    }

    public static void main(String[] args) {
        String str = "dabxabxababxabwabxad";
        String ptr = "abxabwabxad";
        NaiveMatchingString naiveMatchingString = new NaiveMatchingString();
        System.out.println(naiveMatchingString.NaiveMatch(str,ptr)); // 9
    }
}

二：KMP算法核心解決了什么問題弄唧？

子串匹配.png

回想一下樸素匹配算法，當ptr和str進行逐一比較時霍衫，一旦中間哪一個不匹配了候引，str只是往后移動了一個位置，KMP算法核心就是根據(jù)ptr(模式串)匹配中str的部分求得最大的前后綴敦跌，然后根據(jù)這個可以獲得str(主串)往后最大可以移動幾個位置背伴。從而可以節(jié)約時間復雜度。

舉個簡單的例子：

kmp1.png

如上圖峰髓，第一次匹配str(1)=d,ptr(1)=a傻寂，所以不匹配，即str++携兵，第二次匹配一直匹配到str(7)!=ptr(6)疾掰，按照樸素匹配的方式，繼續(xù)將str++徐紧，但是仔細觀察一下ptr匹配中str的部分静檬，即abxab，如果只是簡單的str++,那么第三次開始比較時ptr(2)=b,明顯不會等于a并级。既然我們已經(jīng)從之前匹配中的字符串當中可以看出一些信息拂檩，那么就不需要那么死板的暴力匹配了，那么該如何移動str的位置呢嘲碧？回到abxab這個字符串當中稻励，其前綴包含(a,ab,abx,abxa),不包含最后一個字符，其后綴為(b,ab,xab,bxab)不包含第一個字符，最大的公共前后綴是ab望抽，這說明了啥加矛，說明了可以這樣子移動，見下圖：

kmp2.png

從這里就可以了解到煤篙，KMP算法主要是解決以下問題：
1：通過觀察之前匹配中的字符串斟览，求出最大公共前后綴，使得str往后移動不是漸增辑奈，避免不必要的比較操作苛茂。

三：next數(shù)組怎么求？

上述只是針對匹配中的字符串a(chǎn)bxab的一種解釋鸠窗，可以想象一下味悄，在ptr和str匹配的過程當中，匹配中的字符串存在的可能性有多少種塌鸯，是不是ptr含有多少元素就有多少種侍瑟，而且每種都存在唯一的最大公共前后綴，其實求解這個的過程丙猬，就是求解著名的next數(shù)組涨颜，能夠把這個理解了，KMP算法也就理解了八八九九了茧球，next數(shù)組里面存放的是最大公共前后綴的長度庭瑰，其決定了str每次往后移動的位置個數(shù)。

next數(shù)組.png

接下來對這副圖進行一定的解釋：

• i值表示匹配中ptr字符串的下標抢埋，比如只匹配中a弹灭，下標為0。
• 最右邊的next[i]值揪垄，其實就是我們最終要求得的next數(shù)組穷吮，每個結(jié)點存放的是k值，k值可以理解為匹配中字符串的最大公共子串饥努，可以看到當i=0,1,2時捡鱼，最大的公共前后綴都是0，因為沒有酷愧。
• 解釋一下k驾诈，i指針，i指針很簡單溶浴，每次都指向字符串的最后乍迄，k指針初始下標為0，然后與i下標的值進行比較士败，如果相等闯两，則k++，不相等了，就將當前k的值存入next數(shù)組就好生蚁。
• 進行比較時，k下標和i下標不相等戏自，其實分為兩種情況邦投，第一種情況是第一次比較時相等的，當k++以后(可能存在多次)擅笔，在比較可能存在不相等志衣，這種情況直接將當前的K值存入next數(shù)組就好，還有一種情況猛们，就是第一次比較都不相等念脯，這種情況需要將k = next[k-1]，為什么這么操作弯淘，稍后解釋绿店。獲取新的k值以后，再次進行與i比較庐橙，跟上述流程一樣假勿，這里需要注意的是，當k=0了态鳖，并且第一次比較就不相等转培，那么next[i]直接等于0了。

• 解釋一下為什么當k!=0時浆竭，第一次比較就不相等要讓k=next[k-1]浸须，觀察下圖：

  
  
  kmp3.png
  
  

  假設當i=9時，這時k=4邦泄，最大公共前后綴是abxa删窒，這個abxa的最大最后綴是a，并且k指針現(xiàn)在指向b顺囊。然后當i=10時易稠，i指針指向d，由于k指針指向b包蓝，b!=d驶社，這時候是會觸發(fā)我們剛才說的表達式k=next[k-1]，這樣子测萎，k=1亡电，即指向b，可能這時候就有疑問為什么不指向a硅瞧，要指向b份乒，仔細想想，當i=9時，k指針指向b或辖，b不等于i指針指向的a瘾英，所以導致其最大公共前后綴只有4長度，如果相等了颂暇，那么長度就是5了缺谴。而且abxa的最大公共前后綴是a，那么就可以說明k指針指向的位置b肯定也不會等于i=10時的第一個字符a耳鸯，因為它是abxa的最大公共前后綴湿蛔。所以求k的表達式是k=next[k-1]，這是有講究的县爬。

求解next數(shù)組代碼：

/**
     * 獲取next數(shù)組阳啥，KMP算法的核心。
     * 主要步驟如下：
     * 1财喳、next數(shù)組的大小為ptr.length
     * 2察迟、每次計算最大前后綴的范圍為0-next的下標
     * 3、創(chuàng)建兩個指針耳高，一個為k指針卷拘，一個為i指針，用比較對應下標位置的字符是否一致
     * 4祝高、如果ptr.CharAt(k) == ptr.CharAt(i)栗弟，則k++，如果非第一次比較不相等工闺，則k等于++后的值
     * 5乍赫、如果第一次比較就不相等則k = next[k-1],然后繼續(xù)執(zhí)行與i下標的比較
     * 6、一直循環(huán)至next[ptr.lenth-1],next數(shù)組存放的是k的值
     *
     * @param ptr
     * @return
     */
    public int[] getNext(String ptr) {
        int K = 0; //初始化K指針
        int I; // I指針始終指向最后的位置
        int nextIndex = 1; //表示計算那個next腳標的數(shù)據(jù),因為next[0] = 0陆蟆，從1開始計算
        int[] next = new int[ptr.length()];
        next[0] = 0;
        for (; nextIndex < ptr.length(); ) {
            String substring = ptr.substring(0, nextIndex + 1);
            I = substring.length() - 1;
            if (substring.charAt(K) == substring.charAt(I)) {
                while (K < substring.length() / 2 && substring.charAt(K) == substring.charAt(I)) {
                    K++;
                }
                next[nextIndex++] = K;
            } else {
                if (K == 0){
                    next[nextIndex++] = 0;
                }else{
                    K = next[K - 1];
                    continue;
                }
            }
        }
        return next;
    }

四：KMP算法實現(xiàn)

public class KMPStringMatching {
    /**
     * KMP算法：一種效率匹配子串的算法
     */

    /**
     * 獲取next數(shù)組雷厂，KMP算法的核心。
     * 主要步驟如下：
     * 1叠殷、next數(shù)組的大小為ptr.length
     * 2改鲫、每次計算最大前后綴的范圍為0-next的下標
     * 3、創(chuàng)建兩個指針林束，一個為k指針像棘，一個為i指針，用比較對應下標位置的字符是否一致
     * 4壶冒、如果ptr.CharAt(k) == ptr.CharAt(i)缕题，則k++，如果非第一次比較不相等胖腾，則k等于++后的值
     * 5烟零、如果第一次比較就不相等則k = next[k-1],然后繼續(xù)執(zhí)行與i下標的比較
     * 6瘪松、一直循環(huán)至next[ptr.lenth-1],next數(shù)組存放的是k的值
     *
     * @param ptr
     * @return
     */
    public int[] getNext(String ptr) {
        int K = 0; //初始化K指針
        int I; // I指針始終指向最后的位置
        int nextIndex = 1; //表示計算那個next腳標的數(shù)據(jù),因為next[0] = 0，從1開始計算
        int[] next = new int[ptr.length()];
        next[0] = 0;
        for (; nextIndex < ptr.length(); ) {
            String substring = ptr.substring(0, nextIndex + 1);
            I = substring.length() - 1;
            if (substring.charAt(K) == substring.charAt(I)) {
                while (K < substring.length() / 2 && substring.charAt(K) == substring.charAt(I)) {
                    K++;
                }
                next[nextIndex++] = K;
            } else {
                if (K == 0){
                    next[nextIndex++] = 0;
                }else{
                    K = next[K - 1];
                    continue;
                }
            }
        }
        return next;
    }

    /**
     *
     * @param str:主串
     * @param ptr:模式串
     * @return
     */
    public int getStrIndex(String str,String ptr){
        //先獲取模式串的next數(shù)組
        int[] next = getNext(ptr);
        int str_index = 0; //表示匹配主串的位置
        int str_move_index; //表示匹配主串中移動的位置
        int ptr_index; //表示匹配模式串中的位置
        for (;str_index<=str.length()-ptr.length();){
            for (ptr_index = 0,str_move_index = str_index;ptr.charAt(ptr_index) == str.charAt(str_move_index);ptr_index++,str_move_index++){
                if (ptr_index == ptr.length()-1){
                    return str_index;
                }
            }
            //獲取新的str_index值
            int ne;
            if (ptr_index == 0){
                ne = 0;
                str_index++;
            }else{
                ne = next[ptr_index -1];
                if (ne == 0){
                    str_index++;
                }else{
                    str_index = str_index + (ptr_index - ne);
                }
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        String str = "dabxabxababxabwabxad";
        String ptr = "abxabwabxad";
        KMPStringMatching kmpStringMatching = new KMPStringMatching();
        int strIndex = kmpStringMatching.getStrIndex(str, ptr);
        System.out.println(strIndex); //9
    }
}

kmp4.png