5.7.4　KMP模式匹配算法改进

后来有人发现，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，如图中的⑥。

5.7.4　KMP模式匹配算法改进 - 图1

图5-7-6

我们发现，当中的②③④⑤步骤，其实是多余的判断。由于T串的第二、三、四、五位置的字符都与首位的“a”相等，那么可以用首位next[1]的值去取代与它相等的字符后续next[j]的值，这是个很好的办法。因此我们对求next函数进行了改良。

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

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

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