前些日子写了一篇KMP算法的博文，，在这片文章中，谈到了一个模式串K值的记录数组

next[]，详细可看那篇文章，其实，前面定义的next[]数组是有一定缺陷的，下面我面我将针对一种情况进行举例：

 

  如上图，如果按照之前的方法所获取的next[]数组的话，当两个字符串匹配到上图的情况是，将会出现如下图的情况：

  我们发现，从step1到step3所走的路都是浪费的，因为都是用同一个字母(a)和b去比，而这个计算机也是哼容易识别的，所以对于

next[]的改进是行的通的。

  究其原因，为什么我会说上面的3个步骤是白走的呢，以为这是三个连续的相等的a，因此我们可以从第一步直接跳到第四步，即：得到的数组next[j] = k，而模式串p[j] = p[k]，当主串中的s[i] 和 p[j] 匹配失败时，不需要再和p[k]比较，而直接和p[next[k]]进行比较，当然可以一直迭代往前。

即：

 

代码如下:

void get_nextVal(SString T, int nextVal[]) {     int i = 1, j = 0; nextVal[1] = 0; while( i <= T[0]) { if(j == 0 || T[i] == T[j]) { j++; i++; if(nextVal[i] == nextVal[j]) { nextVal[i] = nextVal[j]; } else { nextVal[i] == j; } } else { j = nextVal[j]; } } }

注意，所求的永远是前一个的K(写给自己的)嘻嘻~~~~~~

use some of my own time, creativity, energy and talent to help people.

http://www.cnblogs.com/Frank-C/p/4909036.html