next数组示例

我们先来看两个next数组的例子

示例1

j123456模式串abcdexnext[j]011111

示例2

j123456模式串abcabxnext[j]011123

求解方式

初始next[1]=0，next[1]=1j逐步递增，在由j前面的字符组成的子串中进行查找，计算next[j]的规则为：子串中最大对称相等的字符个数+1

即： PS：关于nextval数组的求解，可以参考nextval数组如何求解

求解图示

我们以示例2中的例子进行讲解

j=2，子串为a，无对称子串，next[2]=1j=3，子串为ab，首尾不相等，next[3]=1j=4，子串为abc，首尾不相等，next[4]=1j=5，子串为abca，首尾相等，next[5]=1+1=2j=6，子串为abcab，前2个字符和后2个字符相等，next[6]=2+1=3

概括来说，求解next数组的方法为：

在由长度为j-1的子字符串中从以下两个方向找最长的相等字符，next数组的值为最长的字符数+1