2. 计算机
  3. 在KMP模式匹配算法中，需要求解模式串p的next函数值，其定义如下(其中，j为模式串字符的序号)。对于模式串“abaabaca”，其next函数值序列为________。

在KMP模式匹配算法中，需要求解模式串p的next函数值，其定义如下(其中，j为模式串字符的序号)。对于模式串“abaabaca”，其next函数值序列为________。

admin2018-07-25  68
问题 在KMP模式匹配算法中，需要求解模式串p的next函数值，其定义如下(其中，j为模式串字符的序号)。对于模式串“abaabaca”，其next函数值序列为________。
选项 A、01111111
B、01122341
C、01234567
D、01122334
答案B
解析 模式串“abaabaca”的next函数值序列如下：

    当j=1时，next[1]=0；当j=2时，k不存在，next[2]=1；当j=3时，不存在满足条件的k，next[3]=1；当j=4时，p1=p3=a，存在k=2，使得’p1p2…pk-1’=’pj-k+1pj-k+2…pj-1’，故next[4]=2；
当j=5时，存在k=2，使得’p1p2…pk-1’=’pj-k+1+pj-k+2…pj-1’，即p1=p4=a，故next[5]=2；当j=6时，存在k=3，使得’p1p2’=’p4p5’，故next[6]=3；当j=7时，存在k=4，使得’p1p2p3’=’p4p5p6’，故next[7]=4；当j=8时，不存在满足条件的k值，故next[8]=1。
转载请注明原文地址:https://kaotiyun.com/show/85RZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

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