单选题 适中
#22005

在KMP算法中,对于模式串P='abacaba',其next数组(next[i]定义为模式串P[0...i]最长公共前后缀的长度,且数组下标从0开始)的值是什么…

在KMP算法中,对于模式串P='abacaba',其next数组(next[i]定义为模式串P[0...i]最长公共前后缀的长度,且数组下标从0开始)的值是什么?

未登录也能判分,登录后才会记录
答案与解析
正确答案:A
解析

next[i]定义为P[0..i]最长公共前后缀(不能是P[0..i]本身,需同时是前缀与后缀)的长度。  

i=0时,P[0..i]为“a”,长度0;  

i=1时,P[0..i]为“ab”,长度0;  

i=2时,P[0..i]为“aba”,长度1;  

i=3时,P[0..i]为“abac”,长度0;  

i=4时,P[0..i]为“abaca”,长度1;  

i=5时,P[0..i]为“abacab”,长度2;  

i=6时,P[0..i]为“abacaba”,长度3。