当前位置:首页计算机类软件水平考试中级软件设计师->在字符串的KMP模式匹配锋法中,需要求解模式串p的next函

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

中级软件设计师,历年真题,2012年上半年(上午)《软件设计师》真题

  • A.0123123
  • B.0123210
  • C.0123432
  • D.0123456
查看答案 纠错
答案: A
本题解析:

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。

更新时间:2021-11-29 22:09

你可能感兴趣的试题

单选题

(  )is the process of transforming information so it is unintelligible to anyone but the intended recipient.

  • A.Encryption
  • B.Decryption
  • C.Security
  • D.Protection
查看答案
单选题

As each application module is completed,it undergoes(  )to ensure that it operates correctly and reliably.

  • A.unit testing
  • B.integration testing
  • C.system testing
  • D.acceptance testing
查看答案
单选题

(  )algorithm specifies the way to arrange data in a particular order.

  • A.Search
  • B.Random
  • C.Sorting
  • D.Merge
查看答案
单选题

After analyzing the source code,(  )generates machine instructions that will carry out the meaning of the program at a later time.

  • A.an interpreter
  • B.a linker
  • C.a compiler
  • D.a converter
查看答案
单选题

(  )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.

  • A.Data processing system
  • B.Big Data analytics
  • C.Cloud computing
  • D.Database management
查看答案
单选题

浏览器开启无痕浏览模式后,(  )依然会被保存下来。

  • A.浏览历史
  • B.搜索历史
  • C.已下载文件
  • D.临时文件
查看答案
单选题

下列协议中,不属于TCP/IP协议簇的是(  )。

  • A.CSMA/CD
  • B.IP
  • C.TCP
  • D.UDP
查看答案
单选题

下列传输介质中,带宽最宽、抗干扰能力最强的是(  )。

  • A.双绞线
  • B.红外线
  • C.同轴电缆
  • D.光纤
查看答案
单选题

数控编程常需要用参数来描述需要加工的零件的图形。在平面坐标系内,确定一个点需要2个独立的参数,确定一个正方形需要(  )个独立的参数。

  • A.3
  • B.4
  • C.5
  • D.6
查看答案
单选题

某书的页码为1,2,3,...,共用数字900个(一个多位数页码包含多个数字),据此可以推断,该书最大的页码为(  )。

  • A.237
  • B.336
  • C.711
  • D.900
查看答案