关键词：
目录
例题1
例、求串’abaabc’的next数组值__________。
答：首先设next[1]=0，next[2]=1（要注意这里的数组是从1开始的，而不是0），如下表：
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| S | a | b | a | a | b | c |
| next | 0 | 1 |
当j=3时，k=next[j-1]=next[2]=1，
此时看S[j-1]=S[2]='b’与S[k]=S[1]='a’是否相等，
由于不相等，所以继续向前查找next值对应的字符来与前一位进行比较，由于通过查找至第一位仍未找到相等的字符，直接将其赋值，即next[i]=1；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| S | a | b | a | a | b | c |
| next | 0 | 1 | 1 |
当j=4时，k=next[j-1]=next[3]=1，
此时看S[j-1]=S[3]='a’与S[k]=S[1]='a’是否相等，
由于相等，即直接next[j]=k+1=1+1=2；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| S | a | b | a | a | b | c |
| next | 0 | 1 | 1 | 2 |
当j=5时，k=next[j-1]=next[4]=2，
此时看S[j-1]=S[4]='a’与S[k]=S[2]='b’是否相等，
由于S[k]=S[2]='b’与其不相等，所以继续向前查找next值对应的字符来与前一位进行比较，S[2]对应的next值为1，寻找S[1]，找到编号为1的字符，即S[1]=‘a’，
此时比较S[j-1]=S[4]='a’与S[k]=S[1]='a’是否相等，
由于相等，且此时要注意是在第二位S[2]处实现的相等，即
next[j]=next[2]+1=1+1=2；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| S | a | b | a | a | b | c |
| next | 0 | 1 | 1 | 2 | 2 |
当j=6时，k=next[j-1]=next[5]=2，
此时看S[j-1]=S[5]='b’与S[k]=S[2]='b’是否相等，
由于相等，即直接next[j]=k+1=2+1=3；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| S | a | b | a | a | b | c |
| next | 0 | 1 | 1 | 2 | 2 | 3 |
故串’abaabc’的next数组值为011223。
例题2
例、串’ababaaababaa’的next数组值为__________，其next数组为__________。
答：首先设next[1]=0，next[2]=1（要注意这里的数组是从1开始的，而不是0），如下表：
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 |
当j=3时，k=next[j-1]=next[2]=1，
此时看S[j-1]=S[2]='b’与S[k]=S[1]='a’是否相等，
由于不相等，所以继续向前查找next值对应的字符来与前一位进行比较，由于通过查找至第一位仍未找到相等的字符，直接将其赋值，即next[i]=1；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 |
当j=4时，k=next[j-1]=next[3]=1，
此时看S[j-1]=S[3]='a’与S[k]=S[1]='a’是否相等，
由于相等，即直接next[j]=k+1=1+1=2；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 |
当j=5时，k=next[j-1]=next[4]=2，
此时看S[j-1]=S[4]='b’与S[k]=S[2]='b’是否相等，
由于相等，即直接next[j]=k+1=2+1=3；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 |
当j=6时，k=next[j-1]=next[5]=3，
此时看S[j-1]=S[5]='a’与S[k]=S[3]='a’是否相等，
由于相等，即直接next[j]=k+1=3+1=4；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 |
当j=7时，k=next[j-1]=next[6]=4，
此时看S[j-1]=S[6]='a’与S[k]=S[4]='b’是否相等，
由于S[k]=S[4]='b’与其不相等，所以继续向前查找next值对应的字符来与前一位进行比较，S[4]对应的next值为2，寻找S[2]，找到编号为2的字符，即S[2]=‘b’，
此时比较S[j-1]=S[6]='a’与S[k]=S[2]='b’是否相等，
发现依旧不相等，继续查找，S[2]对应的next值为1，寻找S[1]，找到编号为1的字符，即S[1]=‘a’，
此时比较S[j-1]=S[6]='a’与S[k]=S[1]='a’是否相等，
由于相等，且此时要注意是在第二位S[2]处实现的相等，即
next[j]=next[2]+1=1+1=2；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 |
当j=8时，k=next[j-1]=next[7]=2，
此时看S[j-1]=S[7]='a’与S[k]=S[2]='b’是否相等，
由于S[k]=S[2]='b’与其不相等，所以继续向前查找next值对应的字符来与前一位进行比较，S[2]对应的next值为1，寻找S[1]，找到编号为1的字符，即S[1]=‘a’，
此时比较S[j-1]=S[7]='a’与S[k]=S[1]='a’是否相等，
由于相等，且此时要注意是在第二位S[2]处实现的相等，即
next[j]=next[2]+1=1+1=2；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 |
当j=9时，k=next[j-1]=next[8]=2，
此时看S[j-1]=S[8]='b’与S[k]=S[2]='b’是否相等，
由于相等，即直接next[j]=k+1=2+1=3；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 |
当j=10时，k=next[j-1]=next[9]=3，
此时看S[j-1]=S[9]='a’与S[k]=S[3]='a’是否相等，
由于相等，即直接next[j]=k+1=3+1=4；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 |
当j=11时，k=next[j-1]=next[10]=4，
此时看S[j-1]=S[10]='b’与S[k]=S[4]='b’是否相等，
由于相等，即直接next[j]=k+1=4+1=5；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 |
当j=12时，k=next[j-1]=next[11]=5，
此时看S[j-1]=S[11]='a’与S[k]=S[4]='b’是否相等，
由于相等，即直接next[j]=k+1=5+1=6；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 | 6 |
故串’ababaaababaa’的next数组值为011234223456。
将next数组值整体左移一位，低位用-1填充，如下：
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 |
故串’ababaaababaa’的next数组为-1,0,0,1,2,3,1,1,2,3,4,5。
例题3
例、串’ababaaababaa’的nextval数组为___________。
答：可知next数组为：
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 | 6 |
即串’ababaaababaa’的next数组值为011234223456，求nextval数组从0开始，且串的位序由1开始，
首先令nextval[1]=next[1]=0;
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 | 6 |
| nextval | 0 |
从j=2开始进行求nextval数组，判断pj是否等于p(next[j])，若是则将nextval[j]替换为nextval[next[j]]，若不是则nextval[j]=next[j]。
j=2时，p2=b，p(next[2])=p1=a，此时两者不相等，
nextval[2]=next[2]=1；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 | 6 |
| nextval | 0 | 1 |
j=3时，p3=a，p(next[3])=p1=a，此时两者相等，
将nextval[j]替换为nextval[next[j]]，即nextval[3]=nextval[next[3]]=nextval[1]=0；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 | 6 |
| nextval | 0 | 1 | 0 |
j=4时，p4=b，p(next[4])=p2=b，此时两者相等，
将nextval[j]替换为nextval[next[j]]，即nextval[4]=nextval[next[4]]=nextval[2]=1；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 | 6 |
| nextval | 0 | 1 | 0 | 1 |
j=5时，p5=a，p(next[5])=p3=a，此时两者相等，
将nextval[j]替换为nextval[next[j]]，即nextval[5]=nextval[next[5]]=nextval[3]=0；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 | 6 |
| nextval | 0 | 1 | 0 | 1 | 0 |
j=6时，p6=a，p(next[6])=p4=b，此时两者不相等，
nextval[6]=next[6]=4；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 | 6 |
| nextval | 0 | 1 | 0 | 1 | 0 | 4 |
j=7时，p7=a，p(next[7])=p2=b，此时两者不相等，
nextval[7]=next[7]=2；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 | 6 |
| nextval | 0 | 1 | 0 | 1 | 0 | 4 | 2 |
j=8时，p8=b，p(next[8])=p2=b，此时两者相等，
将nextval[j]替换为nextval[next[j]]，即nextval[8]=nextval[next[8]]=nextval[2]=1；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 | 6 |
| nextval | 0 | 1 | 0 | 1 | 0 | 4 | 2 | 1 |
j=9时，p9=a，p(next[9])=p3=a，此时两者相等，
将nextval[j]替换为nextval[next[j]]，即nextval[9]=nextval[next[9]]=nextval[3]=0；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 | 6 |
| nextval | 0 | 1 | 0 | 1 | 0 | 4 | 2 | 1 | 0 |
j=10时，p10=b，p(next[10])=p4=b，此时两者相等，
将nextval[j]替换为nextval[next[j]]，即nextval[10]=nextval[next[10]]=nextval[4]=1；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 | 6 |
| nextval | 0 | 1 | 0 | 1 | 0 | 4 | 2 | 1 | 0 | 1 |
j=11时，p11=a，p(next[11])=p5=a，此时两者相等，
将nextval[j]替换为nextval[next[j]]，即nextval[11]=nextval[next[11]]=nextval[5]=0；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 | 6 |
| nextval | 0 | 1 | 0 | 1 | 0 | 4 | 2 | 1 | 0 | 1 | 0 |
j=12时，p12=a，p(next[12])=p6=a，此时两者相等，
将nextval[j]替换为nextval[next[j]]，即nextval[12]=nextval[next[12]]=nextval[6]=4；
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 | 6 |
| nextval | 0 | 1 | 0 | 1 | 0 | 4 | 2 | 1 | 0 | 1 | 0 | 4 |
可得，故串’ababaaababaa’的nextval数组为0,1,0,1,0,4,2,1,0,1,0,4。
数据结构学习笔记——kmp算法中的常见计算题目总结(代码片段)
目录例题1例题2例题3例题4例题1例、求串’abaabc’的next数组值__________。答：首先设next[1]=0，next[2]=1（要注意这里的数组是从1开始的，而不是0），如下表：编号123456Sabaabcnext01当j=3时，k=n... 查看详情
学习数据结构笔记(18)---[kmp算法](代码片段)
B站学习传送门–>尚硅谷Java数据结构与java算法（Java数据结构与算法）KMP算法这部分看视频讲解的话,还不是很清楚,根据尚硅谷数据结构视频中的推荐,找到这篇很全面的文章—>推荐看大佬的文章–>从头到尾彻底理... 查看详情
专栏必读王道考研408数据结构+计算机算法设计与分析万字笔记题目题型总结注意事项目录导航和思维导图
其他科目导航【专栏必读】王道考研408计算机组成原理万字笔记（从学生角度辅助大家理解）：各章节导航及思维导图【专栏必读】王道考研408操作系统万字笔记（从学生角度辅助大家理解）：各章节导航... 查看详情
机器学习总结笔记
机器学习是什么机器学习为：在进行特定编程的情况下，给予计算机学习能力的领域什么是有监督学习？什么是无监督学习监督学习指的就是我们给学习算法一个数据集（训练集）。这个数据集由“正确答案”组成训练集有输入... 查看详情
机器学习&数据挖掘笔记_16（常见面试之机器学习算法思想简单梳理）
http://www.cnblogs.com/tornadomeet/p/3395593.html机器学习&数据挖掘笔记_16（常见面试之机器学习算法思想简单梳理） 前言： 找工作时（IT行业），除了常见的软件开发以外，机器学习岗位也可以当作是一个选择，不少计算... 查看详情
理解kmp算法(代码片段)
...一下微信搜索程序dunk，关注公众号，获取博主的数据结构与算法的代码笔记目录KMPKMP算法介绍BF(BruteForce)KMP算法计算next数组为什么要进行next回溯[28.实现strStr()](https://leetcode-cn.com/problems/implement-strstr 查看详情
kmp算法_学习笔记
#include<cstdlib>#include<iostream>#include<cstring>usingnamespacestd;int*buildNext(char*P){size_tm=strlen(P),j=0;int*N=newint[m];//next表intt=N[0]=-1;while(j<m-1){if(0>t||P[j]= 查看详情
搜索中常见数据结构与算法探究
...面就用两篇分享来介绍一些本文的主题：第一篇主要介绍数据结构和算法基础和分析方法，以及一些常用的典型的数据结构；第二篇主要介绍图论，以及自动机，KMP，FST等算法；下面开始第一篇2引言“算法是计算机科学领域最... 查看详情
机器学习&数据挖掘笔记_16（常见面试之机器学习算法思想简单梳理）
... 找工作时（IT行业），除了常见的软件开发以外，机器学习岗位也可以当作是一个选择，不少计算机方向的研究生都会接触这个，如果你的研究方向是机器学习/数据挖掘之类，且又对其非常感兴趣的话，可以考虑考虑该岗位，... 查看详情
kmp算法笔记
最近刷了一个Kmp的题目才发现，自己对Kmp算法只是一知半解，就去复习了一下。看了几个版本的算法都感觉不太好，算导的代码感觉不够清晰，其他版本的竟然都是从1开始而非大家习惯的0。经历了各种痛苦之后，终于得到的正... 查看详情
深度学习笔记十一：常见生成模型总结
在前面已经说了生成模型中的GAN系列，这部分简单总结一下常见的生成模型，这里并不需要多少数学，掌握概念就行了，在之后的文章中会详细介绍这些生成模型。 查看详情
常见数据结构与算法整理总结（下）(代码片段)
这篇文章是常见数据结构与算法整理总结的下篇，上一篇主要是对常见的数据结构进行集中总结，这篇主要是总结一些常见的算法相关内容，文章中如有错误，欢迎指出。一、概述二、查找算法三、排序算法四、其它算法五、常... 查看详情
数据结构与算法（下）
这篇文章是常见数据结构与算法整理总结的下篇，上一篇主要是对常见的数据结构进行集中总结，这篇主要是总结一些常见的算法相关内容，文章中如有错误，欢迎指出。一、概述二、查找算法三、排序算法四、其它算法五、常... 查看详情
深度学习算法简要总结系列
...懂PointNet全家桶——强势的点云处理神经网络3D点云深度学习PointNet源码解析——数据预处理【3D计算机视觉】从PointNet到PointNet++理论及pytorch代码【三维目标分类】PointNet++详解（一）数据代码中的数据处理provid... 查看详情
数据结构学习笔记（八大排序算法）整理与总结(代码片段)
数据结构学习笔记（八大排序算法）整理与总结排序的相关概念排序的思想和实现插入排序直接插入排序折半插入排序希尔排序选择排序直接选择排序堆排序交换排序冒泡排序快速排序归并排序基数排序总结参考博客排... 查看详情
数据结构学习笔记（八大排序算法）整理与总结(代码片段)
数据结构学习笔记（八大排序算法）整理与总结排序的相关概念排序的思想和实现插入排序直接插入排序折半插入排序希尔排序选择排序直接选择排序堆排序交换排序冒泡排序快速排序归并排序基数排序总结参考博客排... 查看详情
sklearn|学习总结
...it-learn，又写作sklearn，是一个开源的基于python语言的机器学习工具包。它通过NumPy,SciPy和Matplotlib等python数值计算的库实现高效的算法应用，并且涵盖了几乎所有主流机器学习算法。 SKlearn官网：http://scikit-learn.org/stable/index.html... 查看详情
算法总结二叉树常见算法题目及解题思路汇总(代码片段)
二叉树算法总结主要解决思路：递归自底向上分治栈或队列常见算法题二叉树结构定义如下publicclassTreeNodeintval;TreeNodeleft;TreeNoderight;TreeNode(intx)val=x;1、前序遍历LeetCode144给定一个二叉树，返回它的前序遍历。递归解法pub... 查看详情