当前位置：首页 > news >正文

next数组、nextval数组的推导及C语言实现

news 2025/6/6 11:31:44

1 引言

KMP算法是一种字符串的模式匹配算法，用于获取子串T在主串S中的位置。它对BF（Brute Force）算法进行了改进。KMP算法根据已知的部分匹配结果确定子串T需向右移动的距离，处理了BF算法在匹配过程中主串指针i回溯的问题。而next数组就是对子串向右移动位置的具体描述。

nextval数组是对next数组的改进，处理了next数组的不必要比较。一个例子如下图所示： nextval数组引言

2 next数组定义及推导

定义如下图所示：
next数组定义
推导如下：
next数组推导
补充图：
next数组推导 - 2

3 求next数组（子串T与子串T进行模式匹配）

步骤如下：

求next数组
补充图：
求next数组 - 2

4 next数组的C语言实现

/*函数名：get_next功能描述：求next数组，输入为数组型字符串，输出为next数组
*/
Status get_next(SString T, int next[])
{int j = 1;int k = 0;//初值next[1] = 0;//j的范围：1<=j<=T[0]，T[0]表示串长while (j < T[0]){//若k=0，说明不存在k'<k，根据边界条件，next[j+1]=1，因此，j和k都需要往下移一位//若T[j]=T[k]，next[j+1]=k+1，因此，j和k都需要往下移一位if (k==0 || T[j]==T[k]){++j;++k;next[j] = k;}else{//若T[j]不等于T[k]，则往回找k'k = next[k];}}return OK;
}

5 求nextval数组

步骤如下：

可以看出，nextval数组的求解是在next数组求解的基础上，添加一个步骤。从而有两个求nextval数组的顺序：

每求出一个next[j]，就执行一次添加的步骤，求出当前nextval[j]（适用于计算机求解）
先将整个next数组求出，再对每一个next[j]执行上述添加步骤，从而求出整个nextval数组（考试用）

6 nextval数组的C语言实现

/*函数名：get_nextval功能描述：求nextval数组，输入为数组型字符串，输出为nextval数组
*/
Status get_nextval(SString T, int nextval[])
{int j = 1;int k = 0;//初值nextval[1] = 0;//j的范围：1<=j<=T[0]，T[0]表示串长while (j < T[0]){//若k=0，说明不存在k'<k，根据边界条件，next[j+1]=1，因此，j和k都需要往下移一位//若T[j]=T[k]，next[j+1]=k+1，因此，j和k都需要往下移一位if (k==0 || T[j]==T[k]){++j;++k;if (T[j] != T[k])nextval[j] = k;else//若T[j+1]=T[k+1]，则往回找k'(=nextval[k+1])nextval[j] = nextval[k];}else{//若T[j+1]=T[p]，则往回找p'(=nextval[p])k = nextval[k];}}return OK;
}

7 一个简单的例子

例子如下图所示：
一个简单的例子

先计算next数组值：
- 对j=1，显然j=1，k=0，于是j=2，k=1；
- b不等于a（T(j)与T(k)），于是k=next[1]=0，不存在，从而j=3，k=1；
- a=a，于是j=4，k=2；
- a不等于b，于是k=next[2]=1，a=a，从而j=5，k=2；
- b=b，于是j=6，k=3；
- c不等于a，于是k=next[3]=1，c不等于a，于是k=next[1]=0，不存在，从而j=7，k=1；
- a=a，于是j=8，k=2，结束。
接下来计算nextval数组值：
- j=1，k=0，不存在，于是p=0；
- j=2，k=1，a不等于b（T( p)与T(j)），于是p=1；
- j=3，k=1，a=a，于是p=nextval[1]=0，不存在，从而p=0；
- j=4，k=2，b不等于a，于是p=2；
- j=5，k=2，b=b，于是p=nextval[2]=1，a不等于b，从而p=1；
- j=6，k=3，a不等于c，于是p=3；
- j=7，k=1，a=a，于是p=nextval[1]=0，不存在，从而p=0；
- j=8，k=2，b不等于c，于是p=2，结束。