数据结构(4.5)——next数组的优化

nextVal数组：

 在算出next的解的基础上利用nextVal数组进一步优化算法

首先将nextVal[1]无脑等于0；直接从第二个元素开始看，如果模式串的第j个元素等于模式串第next[j]的话，将nextVal数组第next[j]个元素赋值给nextVal[j]，如果不相等nextVal[j]的值和next[j]相同。

nextVal[1] = 0; // 初始化nextVal数组的第一个元素为0，因为模式串的第一个字符没有前缀

for (int j = 2; j <= T.length; j++) { // 从第二个字符开始遍历模式串
    if (T.ch[next[j]] == T.ch[j]) { // 如果当前字符与前一个字符匹配
        nextVal[j] = nextVal[next[j]]; // 则nextVal[j]等于nextVal[next[j]]，表示当前字符可以与前缀的下一个字符继续比较
    } else {
        nextVal[j] = next[j]; // 否则nextVal[j]等于next[j]，表示当前字符不匹配，需要跳到next[j]的位置继续比较
    }
}

手算方法：

先判断模式串T.ch[next[j]==T.ch[i]? 

等于的情况下：nextVal[j]==nextVal[next[j]；nextval[j]的值需要改变

不等于的情况：nextVal[j]==next[j]；nextVal[j]的值直接等于next[j]

KMP算法优化前：

KMP算法优化后： 

可以发现优化后减少了很多不必要的比较步骤