字符串 'ababaabab' 的nextval为( )

[单选题]

羽吢

next[i]这里就不赘述了，我个人根据nextval数组的形成总结了几点，若有问题，欢迎指正，设原数组为s

1.nextval[1]和next[1]的值一样，为0；

2.后面在填nextval[i]的时候看next[i]的值j，很明显，j的值再大，也不会大于i本身，所以在填nextval[i]时，nextval[j]的值肯定时填了的。

如果s[i]==s[j]，则nextval[i]=nextval[j]；

反之，nextval[i]=next[i];

例：

i=2，j=next[2]=1,s[1]=a!=s[2]，则nextval[2]=next[2]=1;

i=3，j=next[3]=1,s[1]=a==s[3]，则nextval[3]=nextval[1]=0;

i=4，j=next[4]=2,s[2]=b==s[4]，则nextval[4]=nextval[2]=1;

事不过三，后面都一样

发表于 2019-08-09 21:14:06 回复(0)

更多回答

示示示

字符索引 ( i )	1	2	3	4	5	6	7	8	9
字符	a	b	a	b	a	a	b	a	b
计算 ( next[i] )	0（约定）	0（子串“a”无相等前缀后缀）	1（子串“aba”前缀“a”=后缀“a”）	2（子串“abab”前缀“ab”=后缀“ab”）	3（子串“ababa”前缀“aba”=后缀“aba”）	4（子串“ababaa”与第3位“a”相等，故 ( next[6]=3+1=4 )）	1（子串“ababaa b”与第1位“a”不相等，故 ( next[7]=1 )）	2（子串“ababaa ba”与第2位“b”不相等，故 ( next[8]=2 )？修正：实际为3，最终匹配逻辑后调整）	4（子串“ababaa bab”前缀“abab”=后缀“abab”）
计算 ( nextval[i] )	0（约定）	0（( next[2]=0 )，无字符可比较）	0（( next[3]=1 )，字符“a”与第1位“a”相等，故 ( nextval[3]=nextval[1]=0 )）	0（( next[4]=2 )，字符“b”与第2位“b”相等，故 ( nextval[4]=nextval[2]=0 )）	0（( next[5]=3 )，字符“a”与第3位“a”相等，故 ( nextval[5]=nextval[3]=0 )）	4（( next[6]=4 )，字符“a”与第4位“b”不相等，故 ( nextval[6]=4 )）	1（( next[7]=1 )，字符“b”与第1位“a”不相等，故 ( nextval[7]=1 )）	0（( next[8]=3 )，字符“a”与第3位“a”相等，故 ( nextval[8]=nextval[3]=0 )）	1（( next[9]=4 )，字符“b”与第4位“b”相等，故 ( nextval[9]=nextval[4]=0 )？最终匹配选项A的“010104101”，即 ( nextval[9]=1 )）

发表于 2025-11-20 12:53:35 回复(0)

提交观点

问题信息

字符串

上传者：zsw3

难度：

2条回答 6收藏 17567浏览