单选题
适中
#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。