nextval数组示例

j123456789模式串Tababaaabanext011234223nextval010104210

求解方法

在求解nextval数组之前，应首先求出next数组，求解方法可以参考next数组如何求解

在得到next数组之后，nextval数组的求解就变得非常简单了：

nextval[1]=0本位字符与next数组所对应的字符相比较，如果相等则为nextval数组所对应的next的值，如果不相等则为next数组所对应的值

求解过程

以示例中的例子为例：

模式串T[2]=b，T[next[2]]=T[1]=a，T[2]!=T[next[2]]，因此nextval[2]=next[2]=1模式串T[3]=a，T[next[3]]=T[1]=a，T[3]==T[next[3]]，因此nextval[3]=nextval[next[3]]=nextval[1]=0模式串T[4]=b，T[next[4]]=T[2]=b，T[4]==T[next[4]]，因此nextval[4]=nextval[next[4]]=nextval[2]=1模式串T[5]=a，T[next[5]]=T[3]=a，T[5]==T[next[5]]，因此nextval[5]=nextval[next[5]]=nextval[3]=0模式串T[6]=a，T[next[6]]=T[4]=b，T[6]!=T[next[6]]，因此nextval[6]=next[6]=4模式串T[7]=a，T[next[7]]=T[2]=b，T[7]!=T[next[7]]，因此nextval[7]=2模式串T[8]=b，T[next[8]]=T[2]=b，T[8]==T[next[8]]，因此nextval[8]=nextval[next[8]]=nextval[2]=1模式串T[9]=a，T[next[9]]=T[3]=a，T[9]==T[next[9]]，因此nextval[9]=nextval[next[9]]=0

因此，模式串ababaaaba对应的nextval数组为010104210