问题
单项选择题
在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