2. 计算机
  3. 在字符串的KMP模式匹配算法中，需先求解模式串的next函数值，其定义如下式所示，j表示模式串中字符的序号(从1开始)。若模式串p为“abaac”，则其next函数值为( )。

在字符串的KMP模式匹配算法中，需先求解模式串的next函数值，其定义如下式所示，j表示模式串中字符的序号(从1开始)。若模式串p为“abaac”，则其next函数值为( )。

admin2016-05-10  58
问题 在字符串的KMP模式匹配算法中，需先求解模式串的next函数值，其定义如下式所示，j表示模式串中字符的序号(从1开始)。若模式串p为“abaac”，则其next函数值为(   )。
选项 A、01234
B、01122
C、01211
D、1111
答案B
解析 本题考查字符串的模式匹配运算知识。KMP是进行字符串模式匹配运算效率较高的算法。根据对next函数的定义，模式串前两个字符的next值为0、1。对于第3个字符“a”，其在模式串中的前缀为“ab”，从该子串找不出前缀和后缀相同的部分，因此，根据定义，该位置字符的next值为1。对于第4个字符“a”，其在模式串中的前缀为“aba”，该子串只有长度为1的前缀“a”和后缀“a”相同，根据定义，该位置字符的next值为2。对于第5个字符“a”，其在模式串中的前缀为“abaa”，该子串只有长度为l的前缀“a”和后缀“a”相同，根据定义，该位置字符的next值为2。综上可得，模式串“abaac”的next函数值为01122。
转载请注明原文地址:https://www.kaotiyun.com/show/KtRZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

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