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数组的重要性。