1、首先求最大相同前缀后缀长度
模式串的各个子串
前缀
后缀
最大公共元素长度
x
空
空
0
xy
x
y
0
xyx
x ， xy
x ， yx
1 （ x ）
xyxy
x ， xy ， xyx
y ， xy ， yxy
2 （ xy ）
xyxyy
x ， xy ， xyx ， xyxy
y ， yy ， xyy ， yxyy
0
xyxyyx
x ， xy ， xyx ， xyxy ， xyxyy
x ， yx ， yyx ， xyyx ， yxyyx
1 （ x ）
xyxyyxx
x ， xy ， xyx ， xyxy ， xyxyy ， xyxyyx
x ， xx ， yxx ， yyxx ， xyyxx ， yxyyxx
1 （ x ）
xyxyyxxy
x ， xy ， xyx ， xyxy ， xyxyy ， xyxyyx ， xyxyyyxx
y ， xy ， xxy ， yxxy ， yyxxy ， xyyxxy ， yxyyxxy
2 （ xy ）
xyxyyxxyx
x ， xy ， xyx ， xyxy ， xyxyy ， xyxyyx ， xyxyyyxx ， xyxyyyxxy
x ， yx ， xyx ， xxyx ， yxxyx ， yyxxyx ， xyyxxyx ， yxyyxxyx
3 （ xyx ）
模式串
X
Y
X
Y
Y
X
X
Y
X
前缀最大公共元素
0
0
1
2
0
1
1
2
3
严版数据结构求 next 的公式：
我们主要观察第二项，存在两种情况：
（ 1 ）集合为空，若集合为空，则属于公式中的第一或第三种情况（其他情况）， j=1 的时候， next[1]=0 ，当 j>1 的时候， next[j]=1 。
（ 2 ）集合不为空，则我们要取的 k ，是集合中 k 的最大值。
K 需要满足两个条件，一是 1<k<j ，二是后面那个。 -------------------------------------------------------- 对于前面这个，不用多说，对于后面这个，如果只看形式化的公式，估计比较难理解其意义。通过阮老师的博文（http://www.ruanyifeng.com/blog/2013/05/Knuth–Morris–Pratt_algorithm.html），不难理解，后面这个表达式的意义就是所有前缀与所有后缀中，前缀与后缀相同的情况，那么，这个 k 的取值就是前缀与后缀相等时，字符串的长度加上 1 。 -------------------------------------------------------先以严老师书上的例子：
求模式串 abaabcac 的 next 数组
当 j=1 时， next[1]=0 ，直接是公式的第一种情况
当 j=2 时，因为第二种情况要保证集合不为空且 1<k<j ，那么， j=2 时，集合为空，所以不符合第二种情况，因此，属于其他情况，即 next[2]=1
当 j=3 时， k 要小于 j ，所以，我们要在模式串找长度小于 j 的前面全部串的前缀与后缀相同时的最大长度，也就是在模式串中找到前两位 ab ，来找他们最长的前缀与后缀及长度，可以发现，他们没有相同的前缀与后缀，因此，长度为 0 ，而 k 等于长度加 1 ，所以 next[3]=1
当 j=4 时，在 aba 中找前缀与后缀的相同时的最大长度，可以求出最大长度Max为 1 ，所以 next[4]=2
当 j=5 时，在 abaa 中找，Max为 1 ，所以 next[5]=2
当 j=6 时，在 abaab 中找，Max为 2 ，所以 next[6]=3
当 j=7 时，在 abaabc 中找，Max为 0 ，所以 next[7]=1
当 j=8 时，在 abaabca 中找，Max为 1 ，所以 next[8]=2
之所以要找前缀与后缀，是因为我们在比较的时候，避免做多余的工作，即每次遇到主串和模式串不等时，都把模式串直接从头开始比。 -------------------------------------------------------------------
以模式串为 xyxyyxxyx 为例，求 next
当 j=1 ， next[1]=0
当 j=2 ， next[2]=1
当 j=3 ，在 xy 中找前缀与后缀，最大长度 max 为 0 ， next[3]=1
当 j=4 ，在 xyx 中找， Max 为 1 ， next[4]=2
当 j=5 ，在 xyxy 中找， Max 为 2 ， next[5]=3
当 j=6 ，在 xyxyy 中找， Max 为 0 ， next[6]=1
当 j=7 ，在 xyxyyx 中找， Max 为 1 ， next[7]=2
当 j=8 ，在 xyxyyxx 中找， Max 为 1 ， next[8]=2
当 j=9 ，在 xyxyyxxy 中找， Max 为 2 ， next[9]=3
转载于:https://www.cnblogs.com/wts-home/p/11221142.html
相关资源：JAVA上百实例源码以及开源项目