字符串 '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)

提交观点

问题信息

字符串

上传者：zsw3

难度：

1条回答 5收藏 17295浏览

扫一扫，把题目装进口袋