首页 › 题库 › 信息学奥赛 › 6.1 KMP

信息学奥赛-提高级 题库

共 1 道题 · 按题型筛选,点「查看答案」核对解析
1 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 6.1 KMP

在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。

题目详情