KMP（字符串匹配算法）

主串或目標串：比較長的，我們就是在它里面尋找子串是否存在；

子串或模式串：比較短的。

前綴：字符串A和B，A = B+S，S非空，則B為A的前綴。

后綴：A = S+B，S非空，則B為A的后綴。

PMT：前綴集合和后綴集合的交集中，最長前綴的長度。

部分匹配表：PMT值集合，字符串的所有前綴的PMT值。

當出現失配的字符時，我們原來的暴力算法需要將目標串逐個后移，這個過程其實就是拿已經匹配部分的前綴去逐個匹配后綴。如果我們能夠知道每一個位置i處，S[0:i]中已經和后綴匹配的前綴，那么我們是不是就可以直接將前綴和后綴對齊，進而跳過了中間一些字符，然后直接去比較模式串i+1處的字符呢？答案是肯定的。

圖中綠色塊，就是構建next數組過程中，隨著遍歷的深入，前綴和后綴的匹配情況。

其實，我們換一個方向去思考或許更容易：

例如紅色A處失配，那么我們就將目標串往后移動，我們希望移動到模式串的前綴和當前已經遍歷到的目標串的后綴匹配字符最多的地方。

我們需要一個next數組記錄目標串的當前位置失配時，模式串應該轉跳的位置。

next數組與模式串對應。并且next[0] = -1，表示第一個字符沒有匹配的前后綴，如果在0位置失配，只能將目標串后移一位，去和模式串的第二位進行匹配。

next數組中如果某一個元素值為-1，其實就是表示模式串當前位置沒有匹配的前綴，如果在這個位置失配，那么應該直接將目標串的第一位和模式串的下一位比較。

next數組的構造，是通過模式串自己的前綴和后綴匹配進行的。

next[0]=-1;
// 初始化next數組
int i=0,j=-1;//i指向目標串，j指向模式串
while(i<ch.length){if(j==-1){// j=-1，說明，與i匹配的地方是空，那么也就說明，模式串已經到開頭了// 但是還是和目標串不匹配// abab bab b和a不匹配，我們應該將i后移再和j匹配。i+=1;j+=1;}if(ch[i]==ch[j]){i+=1;j+=1;// 當前位置匹配，next[i]的值等于當前位置之前的字符串的PMTnext[i]=j;}else{// 當前位置不匹配，對模式串進行轉跳，// next[j]表示如果在當前位置失配，就應該將模式串的索引轉跳到next[j]位置，繼續匹配j=next[j];}
}

next[i]數組的值表示匹配串的i位置失配了，那么就應該拿模式串的前綴繼續和當前位置匹配，即轉跳到next[i]位置，繼續判斷是否匹配。

public static int KMP(String Str,String Sub,int pos){if (Str == null || Sub == null){return -1;}int i = pos, j = 0;int[] next = new int[Sub.length()];getNext(next,Sub);while(i < Str.length() && j < Sub.length()){if (j == -1 || Str.charAt(i) == Sub.charAt(j)){i++;j++;}else {j = next[j];}}if (j >= Sub.length()){return i-j;}else {return -1;}
}
public static void getNext(int[] next,String sub){next[0] = -1;next[1] = 0;int i = 2,k = 0;while(i < next.length){if (k ==- 1 || sub.charAt(k) == sub.charAt(i-1)){next[i] = k+1;i++;k++;}else {k = next[k];}}
}

示例一

459. 重復的子字符串

/*** 方法一：枚舉法，由于子串至少有兩個，因此，我們枚舉子串的長度1<=k<=n//2;* 方法二：KMP算法，首先先證明一個原理* 假設s的子串為c，且為4個，那么s可以表示為     ccccc* 如果我們將第一個c移動到末尾，那么應該還可以組成s。* 基于這個原理，我們將s復制一份，變成 ss，如果我們刪除ss的第一個字符和最后一個字符* 如果s存在子串c，那么，ss經過刪除前后兩個字符后，中間部分一定還存在和s匹配的字符串*/

示例二

1392. 最長快樂前綴

/*** 思路：kmp算法，首先需要得到字符串s的next數組* 然后，根據題意可知，快樂前綴是和后綴匹配的。那么我們就需要知道，next數組中最后一個位置的數值pos* pos表示，s最后一個數對應的轉跳位置，然后，我們需要進一步比較s[pos]是否等于s[-1]：*   a. 等于，則找到了最長的快樂前綴；*   b. 不等于，pos位置失配，繼續轉跳pos=next[pos];* 直到s[pos]==s[-1]或者pos==-1為止。*/