KMP算法
FBI提示：KMP算法不好了解， 建議視訊+本文+其他部落格，别走馬觀花
KMP算法是用于文本比對的算法，屬于模式搜尋（pattern Searching）問題的一種算法，在講KMP算法之前，傳統的比對字元算法是暴力比對（BF算法）。一個字一個字的比對，直到出現完全比對的情況。
代碼實作：
package cn.dataStructureAndAlgorithm.demo.tenAlgorithm.KMP;
public class 暴力比對算法_字元串比對 {
public static void main(String[] args) {
String str1="auissuie Hello worll? hello worrowhhhello worldss ";
String str2="hello world";
System.out.println(violentMatch(str1,str2));
}
/**
* 暴力比對字元
* @param str1 比對字元區
* @param str2 待比對字元
* @return 比對成功傳回字元串第一個字元下标，否則傳回-1
*/
public static int violentMatch(String str1,String str2){
char[] str1Char=str1.toCharArray();
char[] str2Char=str2.toCharArray();
int str1Len=str1Char.length;
int str2Len=str2Char.length;
int i=0,j=0;//i指向str1,j指向str2
while (i<str1Len && j<str2Len){//不越界時，進行暴力比對
if (str1Char[i]==str2Char[j]){//比對成功
i++;
j++;
}else {//比對失敗
i=i-(j-1);//回溯到先前的之後一個字元
j=0;//置零
}
}
if (j==str2Len){//全字元比對成功
return i-j;
}else{//比對失敗
return -1;
}
}
}
36
暴力比對算法，在大量資料面前，将出現很多次主串索引的回溯（每遇到一個比對失敗就從頭開始），極大的浪費時間。
KMP算法通過省略主串（待比對的雜亂字元串）索引的回溯，盡可能減少反複次數，使字元比對效率有了某種程度的提升
如何省略主串索引的回溯？這需要引入next數組（又稱Profix數組）來記錄從模式串（指定比對的字元串）中提取的加速比對資訊
是不是有點懵，且看圖說話。
上面示範的情景是使用了KMP算法後，失配（主串發現了與模式串不比對）狀況下，模式串的回溯情景
當發現失配時，已經比對過的模式串片段“ABAB”存在有最長公共前字尾“AB”（最長公共前字尾的解釋見下圖），其最長公共前字尾長度為2。
那麼如果将模式串的索引從比對位置移動到下标為2的位置上，且主串索引不動（形象的看就是如圖中，将公共字首部分移動到公共字尾部分）時，就不需要像BF算法（暴力比對）中回溯主串索引再對已經比對過的模式串進行比對判斷（這句話可以畫圖了解一下），進而達到了我們省略主串索引回溯的目的。
随着比對的進行，模式串會被切成很多段
每一段都有自己的最長公共前字尾，到這裡你明白了嗎？使用KMP的核心是什麼？就是找每一段的最長公共前字尾，求出每段對應的最長公共前字尾長度
KMP算法将每段對應的最長公共前字尾，存放在next數組（又稱Profix數組）中。換句話說求出next數組KMP就完成了一大半
第一階段：求next數組
1，示範手動求next數組
有一個提示，模式串的第一段片段“A”，單字元是沒有公共前字尾的，是以對應next值為0。即next[0]=0，這個我們不用求了，直接指派
下圖示範手動求各片段的最長公共前字尾
将求得的各片段最長公共前字尾，放入到對應next數組中，next數組求完了
2，示範程式求next數組
先看圖中流程，後面詳細說。其中i為模式串的索引，len儲存索引前模式串片段的最長公共前字尾長度
制圖不易，擡起你的小手手，關注我一下吧，給我點贊也好啊：>
可以看見，在整個過程中，明顯的存在兩步（字元相等判斷，len值修改）一循環（字元不等且len不為0時重複操作）。其邏輯如下圖
算法流程就是這樣了，接下來說一下為什麼怎麼做？
3，算法分析
在求next數組過程中，首先第一個字元的next值一定為0
有一種情況，當 前一個字元的next值為n時，如果索引為n的模式串字元與目前字元串一緻時，那麼該字元會組成新的最長公共前字尾，自然的，可以将len++的值做為目前字元的next值。這叫繼承。随後i++，進行下一字元判斷
還有一種情況，在上種情況中，兩個字元不等時，我們采用向前再移一位取其next值作為新len值的方式擷取新的len值（這就是len=next[len-1]的由來）取得新的len值後，将進入循環重複字元判斷，修改len值的操作。但要注意一點的是，當字元不等且len值為0時，不能再len-1了，否則将下标越界。這時，直接将0作為字元next的值就可以了，不需要再循環了。（如下圖）随後i++，進行下一字元判斷
上面這個情況下的操作，其實是在尋找前面模式串片段中可能存在的局部小最長公共前字尾（如下圖）
4，代碼實作：
/**
* 提取模式串對應的next數組
* @param str 模式字元串
* @return next數組
*/
public static int[] getNext(String str){
char[] pattern=str.toCharArray();
int[] next=new int[pattern.length];
next[0]=0;
int len=0;
int i=1;
while (i<next.length){
if (pattern[i]==pattern[len]){
len++;
next[i]=len;
i++;
}else {
if (len > 0) {
len = next[len - 1];
} else {
next[i] = len;
i++;
}
}
}
return next;
}
若輸入模式字元串為“ABABCABAA” ，輸出的next數組為
[0, 0, 1, 2, 0, 1, 2, 3, 1]
next數組的值反映了對應模式串片段的對稱程度，如果模式串本身對稱程度低，所得到的next數組就越趨近于0，KMP的比對優化效果越差
如輸入模式字元串為“hello world”，輸出的next數組為
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
至此next數組告一段落，接下來做KMP算法就小case了
第二階段：完成KMP算法主體
KMP流程示意圖如下
不用多說了吧，代碼呈上
KMP比對算法完整代碼實作
package cn.dataStructureAndAlgorithm.demo.tenAlgorithm.KMP;
public class KMP比對算法_字元串比對 {
public static void main(String[] args) {
String str1="ABABABABCABAAB";
String str2="ABABCABAA";
System.out.println(KMP(str1,str2));
}
public static int KMP(String str1,String str2){
int[] next=getNext(str2);
char[] str=str1.toCharArray();
char[] pattern=str2.toCharArray();
int i=0;
int n=0;
while (i<str.length && n<pattern.length){
if (str[i]==pattern[n]){
i++;
n++;
}else {
if (n!=0){
n=next[n-1];
}else {
n=0;
i++;
}
}
}
if (n==pattern.length){
return i-pattern.length;
}else {
return -1;
}
}
/**
* 提取模式串對應的next數組
* @param str 模式字元串
* @return next數組
*/
public static int[] getNext(String str){
char[] pattern=str.toCharArray();
int[] next=new int[pattern.length];
next[0]=0;
int len=0;
int i=1;
while (i<next.length){
if (pattern[i]==pattern[len]){
len++;
next[i]=len;
i++;
}else {
if (len > 0) {
len = next[len - 1];
} else {
next[i] = len;
i++;
}
}
}
return next;
}
}
費半天力氣KMP完成了，現在回顧最開始的“KMP算法通過省略主串（待比對的雜亂字元串）索引的回溯，盡可能減少反複次數，使字元比對效率有了某種程度的提升”這句話，是不是有點感覺了。
有的朋友，為了友善将以上求得的next數組整體右移，在第一個位置添加-1。如“[0, 0, 1, 2, 0, 1, 2, 3, 1]”變為“[-1,0, 0, 1, 2, 0, 1, 2, 3 ]”這樣是為了友善代碼編寫，len=next[len-1]變為len=next[len]，這個看你想不想要了。
KMP中的next數組還可以更新為nextValue數組，該數組對next數組進行了優化。這個優化問題，以後我遇到了，我再填坑。
推薦幾個有關KMP算法的博文
KMP算法的字首next數組最通俗的解釋，如果看不懂我也沒轍了
KMP算法—終于全部弄懂了
其他常用算法，見下各連結
【常用十大算法_二分查找算法】
【常用十大算法_分治算法】
【常用十大算法_貪心算法】
【常用十大算法_動态規劃算法（DP）】
【常用十大算法_普裡姆（prim）算法，克魯斯卡爾（Kruskal）算法】
【常用十大算法_迪傑斯特拉（Dijkstra）算法，弗洛伊德（Floyd）算法】
【常用十大算法_回溯算法】
【資料結構與算法整理總結目錄 ：＞】<-- 寶藏在此（doge）