简介
写这篇文章的主要目的是为了优化上一篇文章中的步骤一。即：优化Next数组的求解方法
与我的上篇文章是有很强的延续性，如果这篇文章看不懂，可以看看我的上一篇文章:KMP算法，你想知道的都在这里(算法理解)
为什么需要优化？
由上一篇可知：我将KMP算法划分为了两个部分：
- 求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均小于i-1的时候，扩大搜索最长公共前后缀
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;
}
- 匹配字符串
/**
* 该函数用于查看目标子串在主串中第一次出现的位置
* @param 目标子串subStr
* @param 主串str
* @param Next数组
* @return str中，第一次出现subStr的位置
*/
static int findPosition(String subStr,String str,int[] Next){
//初始化两个字符串的指针
int i = 0;//i为目标子串的指针
int j = 0;//j为主串的指针
//保证目标子串与主串匹配的过程中，不会越界的情况下：
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;
}
我们不难分析：第一部分的时间复杂度为O(n^2)。第二部分的时间复杂度为O(m)。
这样，KMP算法的总体时间复杂度就是Max(O(n^2),O(m))。那这时候，如果目标子串的长度很长，就会大幅增大整体的计算时间。所以，虽然上述的Next数组求法易于理解，但是不实用。
但是我们不难发现，不管i的数值是多少：subStr[0]和subStr[1]都有经过一次比较，因为subStr[0]必定是前缀的第一个值，而subStr[1]可能是后缀的第一个值，所以可以减少比较次数吗？当然可以，我们必须对其进行剪枝！剪枝策略就是DP
DP策略
我们知道，DP就是有记忆力的暴搜。根据之前的状态，求解后续的状态。DP最重要的就是初始值和状态转移方程！(DP可以专门出一个专题来说)。那这题，我们照例来寻找Next数组的DP策略。
不难发现，Next数组的求解是具有延续性的，Next[i]依赖于Next[i-1]，因为前缀和后缀是相互连续的。
我们已经知道：Next[0]和Next[1]都为0.因为这两个值没有我们定义的前缀和后缀。
初始值：Next[0] = 0, Next[1] = 0
前缀指针profix从0开始，后缀指针suffix从1开始
状态转移： (注意：suffix代表第i个位置的后缀的最后一个位置，所以suffix = i -1。
$$
Next[i] = Next[suffix+1]=\left{ \begin{matrix} Next[i-1]+1---(sub[prefix] = sub[suffix]) \prefix的回溯----- (sub[prefix] ≠ sub[suffix]) \end{matrix} \right.
$$
可以看见，匹配的情况也就两种：前缀指针=后缀指针 与 前缀指针≠后缀指针。
1.前缀指针=后缀指针
这种情况就很好理解了，说明当前位置i的后缀指针suffix与前缀指针prefix指针的值是匹配的，在i-1的最长前后缀的基础上累加即可。i的最长前后缀为：Next[i] = Next[i-1]+1。
2.前缀指针≠后缀指针
这种情况就是当前位置不匹配，说明与后缀相同的前缀一定是小于当前prefix的。
那我们应该回溯，如何回溯呢？想到我们匹配字符串的过程2了吗？
我们可以利用Next数组回溯，Next[prefix]表示0~prefix的串中 最长相等前后缀。所以，不匹配，就让prefix回溯到Next[prefix]。看是否相等，如何仍然不相等就一直回溯。直到相等为止，或者是到位置0为止。
DP代码
//优化Next数组求法，时间复杂度为O(n)
private static int[] CalculateNext(String substr){
//初始化Next数组
int[] Next = new int[substr.length()];
int prefix = 0;
//i就代表suffix+1
for(int i = 2; i < substr.length(); i++){
int suffix = i - 1;
//情况1
while(prefix > 0 && substr.charAt(prefix) != substr.charAt(suffix)){
prefix = Next[prefix];//回溯prefix，直到相等，或为0
}
if(substr.charAt(prefix) == substr.charAt(suffix)){//如果相等就让前缀自增，Next[i] = Next[i-1]+1
prefix++;
}
Next[i] = prefix;
}
return Next;
}
这样，我们就能让KMP算法的时间复杂度控制在O(n)即可
完整代码
我们通过将过程1和过程2进行封装，并对外提供一个接口，整个KMP算法就算完成了！
class KMP {
//对外的KMP算法，返回Str中第一次出现subStr的位置
//如果没有出现subStr,则返回-1
public int kmp(String Str, String subStr) {
//特殊情况：子串为空，返回位置0
if(subStr.equals("")) return 0;
//过程1，求解Next数组
int[] Next = CalculateNext(substr);
//过程2，匹配字符串
return findPosition(subStr,Str,Next);
}
//过程一
private int[] CalculateNext(String substr){
int[] Next = new int[substr.length()];
int prefix = 0;
for(int i = 2; i < substr.length(); i++){
while(prefix > 0 && substr.charAt(prefix) != substr.charAt(i-1)){
prefix = Next[prefix];
}
if(substr.charAt(prefix) == substr.charAt(i-1)){
prefix++;
}
Next[i] = prefix;
}
return Next;
}
//过程一废弃方案，因为时间复杂度过高
// private static int[] CalculateNext(String substr){
// int[] Next = new int[substr.length()];
// for(int i = 2; i < substr.length(); i++){
// int left = 0; int right = i - 1;
// String l = Character.toString(substr.charAt(left));
// String r = Character.toString(substr.charAt(right));
// int maxLen = 0;
// 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;
// }
// Next[i] = maxLen;
// }
// return Next;
// }
//过程二
private int findPosition(String subStr,String str,int[] Next){
int i = 0;
int j = 0;
while(j + subStr.length() - i <= str.length()){
if(subStr.charAt(i) == str.charAt(j)){
i++;j++;
if(i == subStr.length()) return j - subStr.length();
}
else {
if(i == 0) j++;
i = Next[i];
}
}
return -1;
}
}