信息学奥赛-提高级 题库
共 1 道题
· 按题型筛选,点「查看答案」核对解析
1
单选题
适中
在KMP算法中,对于模式串P='abacaba',其next数组(next[i]定义为模式串P[0...i]最长公共前后缀的长度,且数组下标从0开始)的值是什么?
A
{0,0,1,0,1,2,3}
B
{0,1,2,3,4,5,6}
C
{0,0,1,1,2,2,3}
D
{0,0,0,0,1,2,3}
答案与解析
正确答案: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。