问题 单项选择题

在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,使得,故next[4]=2;当j=5时,存在k=2,使得,即P1=P4=a,故next[5]=2;当j=6时,存在k=3,使得,故next[6]=3;当j=7时,存在k=4,使得,故next[7]=4;当j=8时,不存在满足条件的k值,故next[8]=1

单项选择题
多项选择题