KMP算法之从next[]到nextVal[]

前些日子写了一篇KMP算法的博文，浅谈数据结构之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 = , j = ;

     nextVal[] = ;

     while( i <= T[])

     {

         if(j ==  || T[i] == T[j])

         {

             j++;

             i++;

             if(nextVal[i] == nextVal[j])

             {

                 nextVal[i] = nextVal[j];

             }

             else

             {

                 nextVal[i] == j;

             }

         }

         else

         {

             j = nextVal[j];

         }

     }

 }

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

巴特西

KMP算法之从next[]到nextVal[]

最新文章

热门文章