严版数据结构求 next 的公式：
我们主要观察第二项，存在两种情况：
（ 1 ）集合为空，若集合为空，则属于公式中的第一或第三种情况（其他情况）， j=1 的时候， next[1]=0 ，当 j>1 的时候， next[j]=1 。
（ 2 ）集合不为空，则我们要取的 k ，是集合中 k 的最大值。
先以严老师书上的例子：
求模式串 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
KMP算法
这个老师对KMP解析的真心不错，简单易懂！！！
KMP算法是字符串模式匹配的一个改进的算法，此算法可以 在O(m+n)的时间数量级上完成串的模式匹配操作。其主要是求next[]数组。我的这个见解只为了很快求出next[]数组，至于具体的代码实现，还是用经典的代码实现。
KMP算法的思想是当主串中的第i个字符与模式中的第j个字符“失配“（即比较不相等）时，主串中的第i个字符（i不回溯，当然是可以往前加1的）应与模式中的哪个字符比较。（这个可以先不理解，看完就懂啦）
举个例子：
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 模式串 | a | b | a | a | b | c | a | c |
| next[j] | 0 | 1 | 1 | 2 | 2 | 3 | 1 | 2 |
next[j]就是找到p1p2......pj-1这个串中”最长的对称的字符串“。我是加引号的啊，不一定是你想的对称啊！
个人思想：
next[1]为0，next[2]为1，这是不用再算的，也是一定的。我们也没有必要再费心去算。我们从第三个开始。
aba: 其前缀字符串是ab.我们所说的最长的对称子字符串是指这样的对称。如：ab ab 。而不是类似这样的对称，
ab ab a。对，我想表达的意思就是第一个字符串中必须含有第一个字符，第二个字符串中必须含有最后一个字符。所以ab的最长的对称的字符串是0，所以我们的next[3]=0+1=1,对就是最长字符串加1。至于为什么是这样，我想表达一下，却发现很难用语言来说明（原谅我吧）
abaa:其前缀字符串是aba,按我们所说的对称标准，其最长的对称字符串的长度是1，所以其next[4]=1+1=2。
abaab:其前缀字符串是abaa,其最长的对称字符串长度也是1，所以其next[5]=1+1=2;
abaabc:其前缀字符串是abaab,其最长的对称字符串是前后的ab,所以其长度是2，所以next[6]=2+1=3;
abaabca:其前缀字符串是abaabc,是没有我们所说的对称的，所以是0，所以next[7]=0+1=1.注意：这里的p1p2=ab,p4p5=ab,这两个字符串不是我们所要的对称字符串。因为第二个字符串没有包含p6,即pj-1这个字符。
。。。。。。。。。。。。。
//求next数组方法，注意这里的下标从0开始，所以next[0]=-1，计算出结果后，再每位+1。
void buildNext(string& s, int n)
{
int k = -1;
int j = 0;
vector<int> next(n+1);
next[0] = -1;
while(j < n)
{
if(k == -1 || s[j] == s[k])
{
k ++;
j ++;
next[j] = k;
}
else
{
k = next[k];
}
}
}
public static void makeNext(char P[], int next[]) {
int q, k;// q:模版字符串下标；k:最大前后缀长度
int m = P.length;// 模版字符串长度
next[0] = 0;// 模版字符串的第一个字符的最大前后缀长度为0
// for循环，从第二个字符开始，依次计算每一个字符对应的next值
for (q = 1, k = 0; q < m; ++q) {
// 递归的求出P[0]···P[q]的最大的相同的前后缀长度k
while (k > 0 && P[q] != P[k]) {
k = next[k - 1];
}
// 如果相等，那么最大相同前后缀长度加1
if (P[q] == P[k]) {
k++;
}
next[q] = k;
}
System.out.println(Arrays.toString(next));
}
2.假设已知next[j]=k，又T[j] = T[k]，则显然有next[j+1]=k+1；
3.如果T[j]!= T[k]，则令k=next[k]，直至T[j]等于T[k]为止。
注：
1.虽然next定义中没有明确指出next[1]=0，但由0<k<j的条件很容易判断出next[1]只能等于0；
2.next[j]=k表明在T串中的字符T[k]之前存在一个长度最大的子串"tj-ktj-k+1…tj-1"和T串中的子串 "t0t1…tk-1" 相等，而现在又知道了tj=tk，这就是说，在字符T[k+1]之前存在着一个长度最大的子串使得等式 "t0t1…tk"="tj-ktj-k+1…tj"成立，则根据next函数值的定义不就得到next[j+1]=k+1了吗？
3.由于tj!=tk，则等式"t0t1…tk"="tj-ktj-k+1…tj" 不成立，也就是说，在字符T[k+1]之前不存在一个子串" tj-ktj-k+1…tj"和子串"t0t1…tk"相等，那么是否可能存在另一个值p<k，使等式"t0t1…tp"=" tj-ptj-p+1…tj" 成立，这个p显然应该是 next[k]，因为这相当于一个"利用next函数值进行T串和T串的匹配"问题。
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
模式串的各个子串
前缀
后缀
最大公共元素长度
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 ）
2、通过“最长相同前缀后缀长度值右移一位，然后初值赋为 -1 ”得到的 next 数组：
模式串
X
Y
X
Y
Y
X
X
Y
X
前缀最大公共元素
0
0
1
2
0
1
1
2
3
Next
-1
0
0
1
2
0
1
1
2