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

admin2016-05-10  24

问题 在字符串的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://kaotiyun.com/show/KtRZ777K
0

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