KMP演算法，你想知道的都在這裡！
簡潔
我相信很多人都聽說過KMP演算法(PS：在上數據結構的時候，這個演算法自始至終都沒想明白)
大家也知道KMP演算法是用來尋找目標子串的演算法，但是都沒有真正搞懂KMP。之前，我也是如此，我疑惑的有：
- Next數組中的值是如何定下來的？
- 得到Next數組以後，又是如何遍歷的？
希望這篇文章能對你們有所幫助！
影片推薦
KMP這種演算法，單單靠看文章，還是很難弄懂的，結合影像，以及影片的幫助會更容易弄懂。這裡我推薦一個影片：KMP演算法
個人也是通過這個影片，恍然大悟的。這裡還是非常感謝這位作者的分享。
個人總結
通過上述影片，我想大家應該都有一個大概的了解了。該演算法我將它劃分為兩個部分：
- 求Next數組
- 匹配字元串
我將分這兩個部分進行細緻講解
第一部分
求Next數組是KMP演算法的重點，也是難點！想搞懂這部分一定要看影片！一定要看影片！一定要看影片！我覺得上述的影片，將這部分說的很清楚了。這裡做一個總結：(影片里將目標子串的第i號位置映射到Next指針的第i+1號位置。我這裡根據程式設計師的習慣，將目標子串的第i號位置映射到Next指針的第i號位置)
我將Next[i]做一下定義：
/*Next[i]表示：
* 如果(substr.charAt(i) != str.charAt(j))，這時候，將i = Next[i]，再進行字元串匹配。
*/
這種表達雖然不嚴謹，但是我感覺比較直觀hhhh。也即：如果目標子串第i個的值與匹配串第j的值不一致的時候，將目標子串向右滑動，滑動到i = Next[i]。
Next[i]值的定義：
/*Next[i]的值為:
* 第0位為頭的字元串s1，與第i-1為尾的字元串中s2，尋找他們的最長真子串。
* 真子串：這個真子串，就是s1的長度要小於i-1。因為這兩個子串如果是相同的，就沒有意義了
*/
上面這兩個定義值得細品，這也是KMP的精髓，也正是Next數組，KMP演算法才能更加高效！
其中需要注意的點是：Next[0] = 0,Next[1] = 0，因為從第2個開始，s1和s2才有意義。
看完上述定義，我將求Next數組的函數實現出來。註：該函數求Next數組時間複雜度較高，因為是最原始的思路，大家可以想想有什麼簡化的思路，可以在評論區留言，之後我有時間進行改進
/**
* 該函數是為了，根據目標子串subStr，求解該子串的Next數
* @param 目標子串substr
* @return subStr的Next數組
*/
static int[] CalculateNext(String substr){
//init
int[] Next = new int[substr.length()];
//求解Next[i]
for(int i = 2; i < substr.length(); i++){
//第0位為頭的l字元串，與第i-1為尾的r字元串
int left = 0; int right = i - 1;
String l = Character.toString(substr.charAt(left));
String r = Character.toString(substr.charAt(right));
int maxLen = 0;
//當l與r均為真子串的時候
while(left < i - 1){
//如果兩個字元串相同，說明這是目前最長的公共子串
if(l.equals(r)) maxLen = l.length();
left++;
right--;
//繼續擴大搜索範圍
l = l + Character.toString(substr.charAt(left));
r = Character.toString(substr.charAt(right)) + r;
}
//最終的maxLen即為Next[i]的值
Next[i] = maxLen;
}
return Next;
}
第二部分
這個部分就簡單很多了，只要注意一點小細節，整體思路非常清晰直觀：
在保證目標子串與匹配串匹配的過程中，不會越界的情況下：進行目標子串的滑動操作
當subStr.charAt(i) == str.charAt(j)的時候，i與j同時往右移動即可，當完全匹配的時候，就返回
當subStr.charAt(i) ！= str.charAt(j)的時候，i = Next[i]即可。
這裡j需要注意一個細節，如果i == 0，需要j往右移一位，因為第一位都不匹配，前面就再也沒有能匹配的字元串了。
/**
* 該函數用於查看目標子串在匹配串中第一次出現的位置
* @param 目標子串subStr
* @param 匹配串str
* @param Next數組
* @return str中，第一次出現subStr的位置
*/
static int findPosition(String subStr,String str,int[] Next){
//初始化兩個字元串的指針
int i = 0;
int j = 0;
//保證目標子串與匹配串匹配的過程中，不會越界
while(j + subStr.length() - i <= str.length()){
//當匹配的時候，i與j同時往右移
if(subStr.charAt(i) == str.charAt(j)){
i++;j++;
//當完全匹配的時候，返回
if(i == subStr.length()) return j - subStr.length();
}
//不匹配的時候，匹配串指針j只有在i = 0的時候，才右移動。
else {
if(i == 0) j++;
//i值都需要更新
i = Next[i];
}
}
return -1;
}
總結
這裡主要探討的是Next數組，這個是KMP演算法的核心！以前考試都是考Next數組的求解，可見Next數組的重要性。
