KMP的解释，以及代码实现到处都是，请自行google、百度，就不再这里贴了。

相信很多人在求解next数组时遇到了瓶颈，各种博客论坛的解决方案也各不相同，有的甚至是错误的，那么next数组到底是怎么求的呢？

1.在求next数组之前，首先我们求“公有元素个数”，之后求next会用到。
举个例子：

模式串：abaabcac

如何求的呢？

"公有元素个数"就是"前缀"和"后缀"相同的元素的个数。

"a"的前缀和后缀都为空集，公有元素的个数为0；

"ab"的前缀为[a]，后缀为[b]，公有元素的个数为0；

"aba"的前缀为[a, ab]，后缀为[ba, a]，公有元素的个数1；

"abaa"的前缀为[a, ab, aba]，后缀为[baa, aa, a]，公有元素的个数为1；

"abaab"的前缀为[a, ab, aba, abaa]，后缀为[baab, aab, ab, b]，公有元素个数为2；

"abaabc"的前缀为[a, ab, aba, abaa, abaab]，后缀为[baabc, aabc, abc, bc, c]，公有元素个数0；

同理“abaabca”的元素公有个数为1；

“abaabcac”的元素公有个数为0;

2.next函数的定义如下：

next[j]如下：

分析：由next公式可知：

当j=1时，next[j]=0;

当j=2时，由1<k<j可得 1<k<2,因为k是整数，所以，属于第三种情况(其他情况)，所以next[j]=1;

当j>2时，next[j]=k, k-1=前一个的公有元素个数；

所以，next[3] = 1+0 =1；

     next[4] = 1+1 =2；

     next[5] = 1+1 =2;

     next[6] = 1+2 = 3;

     next[7] = 1+0 = 1;

     next[8] = 1+1 = 2;