2. 从业资格
  3. 在字符串的KMP模式匹配锋法中，需要求解模式串p的next函数值，其定义如下所示

在字符串的KMP模式匹配锋法中，需要求解模式串p的next函数值，其定义如下所示

题库2022-08-02  117
问题 在字符串的KMP模式匹配锋法中，需要求解模式串p的next函数值，其定义如下所示。若模式串p为“aaabaaa”，则其next函数值为（　　）。A.0123123B.0123210C.0123432D.0123456
选项 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。
转载请注明原文地址:https://tihaiku.com/congyezige/2410288.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)