一、需要知道的概念

前綴：字串A和B，A=B+S，S非空，則B為A的前綴，
后綴：A=S+B，S非空，則B為A的后綴，
PMT：前綴集合和后綴集合的交集中，最長元素的長度
部分匹配表：PMT值集合，字串所有前綴的PMT值
prefix：每一個下標位置對應一個PMT值，組成的陣列
next：prefix向右移一個下標位置，組成next陣列

下面的圖看不懂不要緊，看完原理就懂了！

例如：
下標5：ABCABC
前綴集合：A，AB，ABC，ABCA，ABCAB
后綴集合：C，BC，ABC，CABC，BCABC
最長交集長度：3（ABC）

二、KMP原理

1.為什么要求交集？

（上面是主串，下面是模式串）
1.開始第一次比較，比較到模式串的最后一位D，與主串A失配，如圖所示：

就要右移模式串繼續比較：

2.其實就是將模式串的前綴BCADBC與主串后綴CADBCA相比較，第一位失配，右移
3.接著前綴BCADB與后綴ADBCA比較，第一位失配，右移
4.接著前綴BCAD與后綴DBCA比較，第一位失配，右移
5.接著前綴BCA與后綴BCA比較，匹配成功

可以發現，每次移動都是前綴集合與后綴集合的比較，尋找主串后綴集合與模式串前綴集合相同的部分（不相同，最后肯定不匹配），即交集，
如果找到交集，就可以直接移過去，省了4步，跳過很多沒必要的操作，

為了將這些交集方便使用，就存盤到PMT陣列內，

2.PMT陣列作用

模式串與主串進行比對時，需要索引，設i為主串索引，j為模式串索引，
當比較到最后一位時，i = 6，j = 6.
有了交集BC，長度為2，這個資訊會存入PMT陣列內，
要提高效率，就要實作對齊，需要移動的元素的位置資訊（即下標）就是交集長度（被保存在PMT陣列中），就是將A移動到D（用 j 記錄）的位置，讓 j 重新指向A的下標2即可，稱為回溯


動態圖演示：
txt主串；pat模式串，

這就是KMP 演算法原理，即永不回退 主串的指標 i，不走回頭路（不會重復掃描 主串），而是借助 PMT 陣列中儲存的資訊把 模式串 移到正確的位置繼續匹配
后面需要求得next陣列，其實和PMT作用一樣，只是為了寫代碼實作方便，

KMP 演算法的難點在于，如何計算 next 陣列中的資訊？如何根據這些資訊正確地移動 模式串 的指標？

3.為什么求模式串的交集

其實，模式串與主串第一次比較的時候，除了失配那一位，失配前那部分都是相同的，
接下來的比較操作，可以理解為那部分的自己前綴和自己后綴比較，

即模式串：BCADBCD，最后一位失配
失配前那部分：BCADBC，
步驟和之前一樣，直到找到交集BC，
如上面所列舉的下標5的例子，找出自己的前綴和后綴的交集，

4.用KMP求next陣列

前提條件：

對于模式串：A B C A B C D
index索引：[ 0, 1, 2, 3, 4, 5, 6 ]
將模式串復制一份（灰色），后移一位，拿灰色前綴與模式串后綴匹配，
先當于再進行一遍KMP演算法，同樣遇到KMP難點，如何計算 next 陣列中的資訊？如何根據這些資訊正確地移動 灰色的指標？
利用KMP 演算法原理，即永不回退 模式串 的指標 i，不走回頭路（不會重復掃描 模式串），而是借助 next 陣列中儲存的資訊把 灰色串 移到正確的位置繼續匹配

i 是模式串的索引，j是灰色的索引
為了當不匹配時，讓灰色后移后，繼續與模式串下一位開始比較，需要i++，j++，并且使得 j 要從0開始（從灰色第一個元素開始），就需要以 j= -1為灰色整體右移資訊，即失配時就要置為-1，正好j+1=0，

匹配時，j++即可，
如此一來，j就提供了資訊：j的值 就是灰色與模式串在 i 之前匹配的個數，也就是交集的長度，也就是PMT[ i ]所需要的值，也就是next[i+1]的值，

思考一下，next[ j ]存盤的內容和 j 的關系？
next[ j ] = PMT[ j - 1 ]
就是 j所指位置 的前一位置的匹配個數，即交集長度，
如果 j所指的位置失配， 就需要移動灰色串，要移動多少呢？（j要指向下標是多少呢？）
資訊就在next [ j ]里，即令j = next [ j ] 來實作回溯，
next陣列代替PMT陣列帶來的編碼好處就體現出來了

第一步：i=0，
i 指向的 A（紅色標記），只有一個元素沒有前后綴，所以沒有交集.j=-1
PMT [ 0 ]=0，next [ 0 ]= -1，
使 i 和 j 右移，進行下一次比對

第二步：i = 1，j=0
next[i]的值，是上一步PMT[i]的值（記錄上一步交集長度，匹配的元素個數，j的值）,next[ 1 ] = PMT[ 0 ] = 0；
j 指向索引0的位置A，失配
j = next [ 0 ] = -1;
使 i 和 j 右移，進行下一次比對

第三步：i = 2，
j指向索引0的位置A，失配
j = next [0] = -1，使 i 和 j 右移，進行下一次比對

第四步：i = 3，
j=0 ，j指向索引0的位置A，匹配
j=j+1=1,使 i 和 j 右移，進行下一次比對
有交集，給陣列賦值
PMT [ 3 ] = 1 ，
next[ 3 ] = 0

第五步：i = 4，j =1， 匹配，給陣列賦值
使 i 和 j 右移，進行下一次比對

第六步：i = 5，j = 2，匹配，給陣列賦值
使 i 和 j 右移，進行下一次比對

第七步：i = 6，j = 3
i指向D，j指向索引3的位置A，失配

代碼

//字串匹配
    static int search(char[] str,char[] pattern,int[] next){
        int i = 0;
        int j = 0;

        while (i< str.length&&j< pattern.length){
            if (j==-1||str[i] == pattern[j]){
                i++;
                j++;
            }
            else{
                j = next[j];			//回溯，右移
            }
        }
        if (j== pattern.length)
            return i - 1;
        else {
            return -1;
        }
    }
//求模式串的next陣列
    static void getNext(char[] pattern,int[] next){
        next[0] = -1;
        int i = 0,j = -1;

        while (i< pattern.length){
            if(j == -1){                //，j=-1，空
                i++;
                j++;
            }else if (pattern[i] == pattern[j]){
                i++;j++;
                next[i] = j;
            }else {
                j = next[j];			//回溯，右移
            }
        }
    }