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

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

题库2022-08-02  45
问题 在字符串的KMP模式匹配算法中，需先求解模式串的next函数值，其定义如下式所示，j表示模式串中字符的序号（从1开始）。若模式串p为“abaac”，则其next函数值为（　　）。A.01234B.01122C.01211D.01111
选项 A.01234
B.01122
C.01211
D.01111
答案 B
解析 ＜k＜k＜k＜j的数k，由（3）式，next[2]=1；
＜k＜j的数k=2，同时需要满足'p1p2lpk-1'="pj-k+1pj-k+2Lpj-1"。
＜k＜j的数k=2或3：
＜k＜j的数k=2、3或4：
本题考查字符串的模式匹配运算知识。
KMP是进行字符串模式匹配运算效率较高的算法。根据对next函数的定义，模式串前两个字符的next值为0、1。对于第3个字符“a”，其在模式串中的前缀为“ab”，从该子串找不出前缀和后缀相同的部分，因此，根据定义，该位置字符的next值为1。
对于第4个字符“a”，其在模式串中的前缀为“aba”，该子串只有长度为1的前缀“a”和后缀“a”相同，根据定义，该位置字符的next值为2。
对于第5个字符“a”，其在模式串中的前缀为“abaa0”，该子串只有长度为1的前缀“a”和后缀“a”相同，根据定义，该位置字符的next值为2。
综上可得，模式串“abaac”的next函数值为01122。
一、对于公式：
1、由（1）式，当j=1时，next[1]=0；
2、当j=1时，由（2）式，max{k|1＜k＜k3、取值范围，j、k都为正整数，且1＜=j＜=5
【可根据下面的具体过程理解公式】
二、本题计算如下：
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，同时需要满足'p1p2lpk-1'="pj-k+1pj-k+2Lpj-1"。
'p1p2Lpk-1'='p1p2Lp1'=p1，为第一个字母a；'pj-k+1pj-k+2Lpj-1'='p2p3Lp2'=p2，为第二个字母b，a!=b，此时，找不到k不满足条件，由（3）式，next[3]=1。
4、j=4，满足1＜k＜j的数k=2或3：
（1）当k=2，'p1p2Lpk-1'='p1p2Lp1'=p1，为第一个字母a，'pj-k+1pj-k+2Lpj-1'='p3p4Lp3'=p3，为第三个字母a，满足'p1p2Lpk-1'='pj-k+1pj-k+2Lpj-1'。
（2）当k=3，'p1p2Lpk-1'='p1p2Lp2'=p1p2，为第一二字母ab，'pj-k+1pj-k+2Lpj-1'='p2p3Lp3'=p2p3，为第二三个字母ba，不满足'p1p2Lpk-1'='pj-k+1pj-k+2Lpj-1'。
综上可得，当j=4时，满足条件的最大k值为2，next[4]=2。
5、j=5，满足1＜k＜j的数k=2、3或4：
（1）当k=2，'p1p2Lpk-1'='p1p2Lp1'=p1，为第一个字母a，'pj-k+1pj-k+2Lpj-1'='p4p5Lp4'=p4，为第四个字母a，满足'p1p2Lpk-1'='pj-k+1pj-k+2Lpj-1'。
（2）当k=3，'p1p2Lpk-1'='p1p2Lp2'=p1p2，为第一二字母ab，'pj-k+1pj-k+2Lpj-1'='p3p4Lp4'=p3p4，为第三四个字母aa，不满足'p1p2Lpk-1'='pj-k+1pj-k+2Lpj-1'。
（3）当k=4，'p1p2Lpk-1'='p1p2Lp3'=p1p2p3，为第一二三字母aba，'pj-k+1pj-k+2Lpj-1'='p2p3Lp4'=p2p3p4，为第二三四个字母baa，不满足'p1p2Lpk-1'='pj-k+1pj-k+2Lpj-1'。
综上可得，当j=5时，满足条件的最大k值为2，next[5]=2。
根据上面的分析过程，可以得出next[]函数值为01122。
转载请注明原文地址:https://tihaiku.com/congyezige/2409828.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

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