后来有人发现，KMP还是有缺陷的。比如，如果我们的主串S=”aaaabcde”，子串T=”aaaaax”，其next数组值分别为012345，在开始时，当i=5、j=5时，我们发现“b”与“a”不相等，如图5-7-6的①，因此j=next[5]=4，如图中的②，此时“b”与第4位置的“a”依然不等，j=next[4]=3，如图中的③，后依次是④⑤，直到 j=next[1]=0时，根据算法，此时i++、j++，得到 i=6、j=1，如图中的⑥。
    image.png
    我们发现，当中的②③④⑤步骤，其实是多余的判断。由于T串的第二、三、四、五位置的字符都与首位的“a”相等，那么可以用首位 next[1]的值去取代与它相等的字符后续next[j]的值，这是个很好的办法。因此我们对求next函数进行了改良。

    假设取代的数组为nextval，增加了加粗部分，代码如下：

    1. /* 求模式串T的next函数修正值并存入数组
    2. nextval */
    3. void get_nextval(String T, int *nextval){
    5.     int i, j;
    6.     i = 1;
    7.     j = 0;
    8.     nextval[1] = 0;
    10.     /* 此处T[0]表示串T的长度 */
    11.     while (i < T[0]){
    13.         /* T[i]表示后缀的单个字符， */
    14.         /* T[j]表示前缀的单个字符 */
    15.         if (j == 0 || T[i] == T[j]){
    17.             ++i;
    18.             ++j;
    20.             /* 若当前字符与前缀字符不同 */
    21.             if (T[i] != T[j])
    22.                 /* 则当前的j为nextval在i位置的值 */
    23.                 nextval[i] = j;
    24.             else
    25.                 /* 如果与前缀字符相同，则将前缀 */
    26.                 /* 字符的nextval值赋值给nextval在i位置的值 */
    27.                 nextval[i] = nextval[j];
    29.         }
    30.         else
    31.         /* 若字符不相同，则j值回溯 */
    32.         j = nextval[j];
    34.     } 
    36. }

    实际匹配算法，只需要将“get_next(T,next);”改为“get_nextval(T,next);”即可，这里不再重复。