i 0 1 2 3 4 5 6 7 8 9 10 11 s a b a b a a a b a b a a next[i] -1 0 0 1 2 3 1 1 2 3 4 5 先计算前缀next[i]的值： （字符串匹配是 从头开始的 和 从尾开始的字符串进行匹配是否重复 ） next[i]的值主要是看s[i]之前的字符串中重复的子串长度。next[0] = -1，定值。 next[1]是看s[1]之前的字符串“a”中重复的子串长度为0，故next[1] = 0。 next[2]是看s[2]之前的字符串“ab”中重复的子串长度为0，故next[2] = 0。 next[3]是看s[3]之前的字符串"aba"中重复的子串长度，s[0]与s[2]重复，长度为1，故next[3] = 1。 next[4]是看s[4]之前的字符串"abab"中重复的子串长度，s[01]与s[23]重复，长度为2，故next[4] = 2。 next[5]是看s[5]之前的字符串"ababa"中重复的子串长度，s[012]与s[234]重复，长度为3，故next[5] = 3。 next[6]是看s[6]之前的字符串"ababaa"中重复的子串长度，s[0]与s[5]重复(因为多了一个a，无法找到长度为3的重复字符串，这只能是s[0]和s[5]重复)，长度为1，故next[6] = 1。 同样的，求next[7]和next[8]、next[9]、 next[10]、 next[11] 分别为1和2、3、4、5。

总结： 1、next数组首个位置数值为定值-1 2、next[i]的值是看在s[i]之前的字符串中重复的子串长度（1、不统计第i位置的字符2、两个子串一个必须从首位置开始，另一个必须从尾位置结束）