数据结构学习笔记——KMP算法中的常见计算题目总结_数据结构kmp算法例题

例题1

例、求串’abaabc’的next数组值__________。

答：首先设next[1]=0，next[2]=1（要注意这里的数组是从1开始的，而不是0），如下表：

当j=3时，k=next[j-1]=next[2]=1，
此时看S[j-1]=S[2]='b’与S[k]=S[1]='a’是否相等，
由于不相等，所以继续向前查找next值对应的字符来与前一位进行比较，由于通过查找至第一位仍未找到相等的字符，直接将其赋值，即next[j]=next[3]=1；

当j=4时，k=next[j-1]=next[3]=1，
此时看S[j-1]=S[3]='a’与S[k]=S[1]='a’是否相等，
由于相等，即直接next[j]=next[4]=k+1=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[5]=next[2]+1=1+1=2；

当j=6时，k=next[j-1]=next[5]=2，
此时看S[j-1]=S[5]='b’与S[k]=S[2]='b’是否相等，
由于相等，即直接next[j]=next[6]=k+1=2+1=3；

故串’abaabc’的next数组值为011223。

例题2

例、串’ababaaababaa’的next数组值为__________，其next数组为__________。

答：首先设next[1]=0，next[2]=1（要注意这里的数组是从1开始的，而不是0），如下表：

当j=3时，k=next[j-1]=next[2]=1，
此时看S[j-1]=S[2]='b’与S[k]=S[1]='a’是否相等，
由于不相等，所以继续向前查找next值对应的字符来与前一位进行比较，由于通过查找至第一位仍未找到相等的字符，直接将其赋值，即next[j]=next[3]=1；

当j=4时，k=next[j-1]=next[3]=1，
此时看S[j-1]=S[3]='a’与S[k]=S[1]='a’是否相等，
由于相等，即直接next[j]=next[4]=k+1=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]=next[5]=k+1=2+1=3；

当j=6时，k=next[j-1]=next[5]=3，
此时看S[j-1]=S[5]='a’与S[k]=S[3]='a’是否相等，
由于相等，即直接next[j]=next[6]=k+1=3+1=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[7]=next[2]+1=1+1=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[8]=next[2]+1=1+1=2；

当j=9时，k=next[j-1]=next[8]=2，
此时看S[j-1]=S[8]='b’与S[k]=S[2]='b’是否相等，
由于相等，即直接next[j]=next[9]=k+1=2+1=3；

当j=10时，k=next[j-1]=next[9]=3，
此时看S[j-1]=S[9]='a’与S[k]=S[3]='a’是否相等，
由于相等，即直接next[j]=next[10]=k+1=3+1=4；

当j=11时，k=next[j-1]=next[10]=4，
此时看S[j-1]=S[10]='b’与S[k]=S[4]='b’是否相等，
由于相等，即直接next[j]=next[11]=k+1=4+1=5；

当j=12时，k=next[j-1]=next[11]=5，
此时看S[j-1]=S[11]='a’与S[k]=S[4]='b’是否相等，
由于相等，即直接next[j]=next[12]=k+1=5+1=6；

故串’ababaaababaa’的next数组值为011234223456。

将next数组值整体左移一位，低位用-1填充，如下：

故串’ababaaababaa’的next数组为-1,0,0,1,2,3,1,1,2,3,4,5。

例题3

例、已知字符串S=‘aabaabaabaac’，模式串P=‘aabaac’，求P的next数组值以及具体的KMP算法匹配过程。

答：首先设next[1]=0，next[2]=1（这里设数组是从1开始的，而不是0），如下表：

当j=3时，k=next[j-1]=next[2]=1，
此时看S[j-1]=S[2]='a’与S[k]=S[1]='a’是否相等，
由于相等，即直接next[j]=next[3]=k+1=1+1=2；

当j=4时，k=next[j-1]=next[3]=2，
此时看S[j-1]=S[3]='b’与S[k]=S[2]='a’是否相等，
由于S[k]=S[2]='a’与其不相等，所以继续向前查找next值对应的字符来与前一位进行比较，S[2]对应的next值为1，寻找S[1]，找到编号为1的字符，即S[1]=‘a’，
此时比较S[j-1]=S[3]='b’与S[k]=S[1]='a’是否相等，
由于不相等，所以继续向前查找next值对应的字符来与前一位进行比较，由于通过查找至第一位仍未找到相等的字符，直接将其赋值，即next[j]=next[4]=1；

当j=5时，k=next[j-1]=next[4]=1，
此时看S[j-1]=S[4]='a’与S[k]=S[1]='a’是否相等，
由于相等，即直接next[j]=next[5]=k+1=1+1=2；

当j=6时，k=next[j-1]=next[5]=2，
此时看S[j-1]=S[5]='a’与S[k]=S[2]='a’是否相等，
由于相等，即直接next[j]=next[6]=k+1=2+1=3；

可知当主串与模式串进行匹配时，当i=6，j=6时，发生失配，通过next数组值表，可知，next[6]=3，即此时主串当前位置与模式串的第三个字符进行比较，如下：

然后，发现当i=9，j=6时，又发生失配，如下：

最后匹配成功。

例题4

例、串’ababaaababaa’的nextval数组为___________。

答：可知next数组为：

即串’ababaaababaa’的next数组值为011234223456，求nextval数组从0开始，且串的位序由1开始，
首先令nextval[1]=next[1]=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；

j=3时，p3=a，p(next[3])=p1=a，此时两者相等，
将nextval[j]替换为nextval[next[j]]，即nextval[3]=nextval[next[3]]=nextval[1]=0；

j=4时，p4=b，p(next[4])=p2=b，此时两者相等，
将nextval[j]替换为nextval[next[j]]，即nextval[4]=nextval[next[4]]=nextval[2]=1；

j=5时，p5=a，p(next[5])=p3=a，此时两者相等，
将nextval[j]替换为nextval[next[j]]，即nextval[5]=nextval[next[5]]=nextval[3]=0；

j=6时，p6=a，p(next[6])=p4=b，此时两者不相等，
nextval[6]=next[6]=4；

j=7时，p7=a，p(next[7])=p2=b，此时两者不相等，
nextval[7]=next[7]=2；

j=8时，p8=b，p(next[8])=p2=b，此时两者相等，
将nextval[j]替换为nextval[next[j]]，即nextval[8]=nextval[next[8]]=nextval[2]=1；

j=9时，p9=a，p(next[9])=p3=a，此时两者相等，
将nextval[j]替换为nextval[next[j]]，即nextval[9]=nextval[next[9]]=nextval[3]=0；

j=10时，p10=b，p(next[10])=p4=b，此时两者相等，
将nextval[j]替换为nextval[next[j]]，即nextval[10]=nextval[next[10]]=nextval[4]=1；

j=11时，p11=a，p(next[11])=p5=a，此时两者相等，
将nextval[j]替换为nextval[next[j]]，即nextval[11]=nextval[next[11]]=nextval[5]=0；

j=12时，p12=a，p(next[12])=p6=a，此时两者相等，
将nextval[j]替换为nextval[next[j]]，即nextval[12]=nextval[next[12]]=nextval[6]=4；

可得，故串’ababaaababaa’的nextval数组为0,1,0,1,0,4,2,1,0,1,0,4。