在KMP算法中,如果模式串为'ababaca',则next数组为?
答案解析
对于模式串'ababaca',其next数组计算过程如下:首先,next[0]固定为0。对于位置1的字符'b',没有前缀和后缀匹配,next[1]=0。对于位置2的字符'a',前缀'a'和后缀'a'匹配,next[2]=1。对于位置3的字符'b',前缀'ab'和后缀'ab'匹配,next[3]=2。对于位置4的字符'a',前缀'aba'和后缀'aba'匹配,next[4]=3。对于位置5的字符'c',没有更长的前缀和后缀匹配,next[5]=0。对于位置6的字符'a',前缀'a'和后缀'a'匹配,next[6]=1。因此,正确的next数组为[0, 0, 1, 2, 3, 0, 1],选项A正确。选项B、C和D的计算结果与正确结果不符。
正确答案:A