求next与nextval数组值

next数组值求解

以上面的串s为例

next数组值第1位为0

第2位为1，因为字符b前面就一个字符a，没有其他字符了，即next为0+1=1

从第3位a开始，因为第2位的next值为1，所以查找ab子串的前1位和后1位，也就是前缀1位为a，后缀1位为b，a与b不相等，则next为0+1=1.

第4位b，因为第3位的next值为1，和上面一样查找aba子串的前缀1位和后缀1位，也就是a与a，a与a相等，即第4位的next值为1+1=2

第5位a，因为第4位的next值为2，和上面一样查找abab子串的前缀2位和后缀2位，也就是ab与ab，ab与ab相等，即第5位的next的值为2+1=3（其中2是匹配相等子串的长度）

第6位a，因为第5位的next值为3，和上面一样查找ababa子串的前缀3位和后缀3位，也就是aba与aba，aba与aba相等，即第6位的next值为3+1=4

第7位a，因为第6位的next值为4，即对子串ababaa查找前缀4位和后缀4位，发现最大公共子串为a，即第7位的next值为1+1=2

下面以此类推

最后得到结果

nextval数组值求解

第1位与第2位依然是0与1

从第3位开始，注意观察其下标3与第3位对应的next值，next值为1，观察下标1与3对应的串值是否相等，可得，a与a相等，则第3位的nextval值与第1位的nextval值相等，即第3为的nextval值为0

第4位，观察下标4与其对应的next值为2，则查看第2位与第4位的串值，b与b相等，则第4位的nextval值与第2位的nextval值相等为1

第5位，观察下标5与其对应的next值为3，a与a相等，则第5位的nextval值为0

第6位，观察下标6与其对应的next值为4，串下标为4对应的串值元素为b，a与b不相等，则第6位的nextval就是它本身的next值，即nextval=4

剩下的都是按照同样的方法，以下是s串完整的next与nextval值