问题 问答题

令s=‘aaab’,t=‘abcabaa’,u=‘abcaabbabcabaacbacba’,分别求出它们的next值。

答案

参考答案:

解析:当位置j=1时,next[j]=0;当位置j>1时,next[j]的值为模式串的位置1到j-1构成的串中所出现的首尾相同的子串的最大长度加l,无首尾相同的子串时next[j]的值为1。本题答案如下表所示:

j1234567
模式串saaab
next[j]0123
模式串sabcabaa
next[j]0111232

j12345678910
模式串uabcaabbabc
next[j]0111223123
j11121314151617181920
模式串uabcabaa
nect[j]4532211211

选择题
单项选择题