在字符串的KMP模式匹配锋法中,需要求解模式串p的next函数值,其定义如下所示。若模式串p为“aaabaaa”,则其next函数值为( )。

KMP模式匹配算法通俗点说就是一种在一个字符串中定位另一个串的高效算法。其实我们在做这个题目时,也可以不需要知道KMP模式匹配算法,可以根据题目给出的定义式来求解。
【对于本题公式】
1、当j=1时,由(1)式,next[1]=0;
2、当j!=1时,由(2)式,max{k|1<k<j'p1p2...pk-1'='pj-k+1pj-k+2...pj-1'},即选择符合要求的最大k值,要求:1<k<j,并且满足'p1p2...pk-1'='pj-k+1pj-k+2...pj-1',如果有满足要求的k值,则next[j]=max{k};如果找不到满足条件的k值,则由(3)式next[j]=1。
3、取值范围,j、k都为正整数,且1<=j<=5
【求取next[]过程如下】
1、当j=1时,由(1)式,next[1]=0;
2、当j=2时,找不到满足1<k<j的数k,由(3)式,next[2]=1;
3、当j=3时,满足1<k<j的数k=2,同时需要满足'p1p2...pk-1'='pj-k+1pj-k+2...pj-1'。'p1p2...pk-1'='p1p2...p1'=p1,为第一个字母a;'pj-k+1pj-k+2...pj-1'='p2p3...p2'=p2,为第二个字母a,此时,k满足条件,由(2)式,next[3]=k=2。
4、当j=4时,满足1<k<j的数k=2或3:
(1)当k=2,'p1p2...pk-1'='p1p2...p1'=p1,为第一个字母a,'p1p2...pk-1'='p3p4...p3'=p3,为第三个字母a,满足'p1p2...pk-1'='pj-k+1pj-k+2...pj-1'。
(2)当k=3,'p1p2...pk-1'='p1p2...p2'=p1p2,为第一二字母aa,'pj-k+1pj-k+2...pj-1'='p2p3...p3'=p2p3,为第二三个字母aa,'p1p2...pk-1'='pj-k+1pj-k+2...pj-1'。
因此next[4]=max{2,3}=3。
5、j=5,满足1<k<j的数k=2、3或4:
(1)当k=2,'p1p2...pk-1'='p1p2...p1'=p1,为第一个字母a,'p1p2...pj-1'='p4p5...p4'=p4,为第四个字母b,不满足'p1p2...pk-1'='pj-k+1pj-k+2...pj-1'。
(2)当k=3,'p1p2...pk-1'='p1p2...p2'=p1p2,为第一二字母aa,'pj-k+1pj-k+2...pj-1'='p3p4...p4'=p3p4,为第三四个字母ab,不满足'p1p2...pk-1'='pj-k+1pj-k+2...pj-1'。
(3)当k=4,'p1p2...pk-1'='p1p2Lp3'=p1p2p3,为第一二三字母aaa,'pj-k+1pj-k+2...pj-1'='p2p3...p4'=p2p3p4,为第二三四个字母aab,不满足'p1p2...pk-1'='pj-k+1pj-k+2...pj-1'。
因此,当j=5时,没有满足条件k,此时由(3)式,next[5]=1。
同理我们可以求得当j=6,j=7的结果,本题正确答案选A。
( )is the process of transforming information so it is unintelligible to anyone but the intended recipient.
As each application module is completed,it undergoes( )to ensure that it operates correctly and reliably.
( )algorithm specifies the way to arrange data in a particular order.
After analyzing the source code,( )generates machine instructions that will carry out the meaning of the program at a later time.
( )can help organizations to better understand the information contained within the data and will also help identify the data that is most important to the business and future business decisions.
浏览器开启无痕浏览模式后,( )依然会被保存下来。
下列协议中,不属于TCP/IP协议簇的是( )。
下列传输介质中,带宽最宽、抗干扰能力最强的是( )。
数控编程常需要用参数来描述需要加工的零件的图形。在平面坐标系内,确定一个点需要2个独立的参数,确定一个正方形需要( )个独立的参数。
某书的页码为1,2,3,...,共用数字900个(一个多位数页码包含多个数字),据此可以推断,该书最大的页码为( )。