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;
总结：
其实我们来看next[1],next[2],是必等与0和1的。当j>2时，我们可以用 (k=next[j],next[j]=1+前一个的公有元素个数) 这个公式来求。
牛客网上有人算得“aaab”这个字符串是0120应该是用的阮一峰老师的部分匹配表那种方法，也是可以，不过要注意人家是要你求next[j]还是部分匹配表。
其实字符串匹配速度最快的是Boyer-Moore这种算法，好像ctrl+F都是用的这个。
网友评论