kmp算法的nextval数组怎么求



例：给出一个字符串序列：ababaaababaa。利用KMP算法分别求出next数组和nextval数组
分析：
数组索引：0-n
逻辑索引：1-n

next数组：

1、next[0]=0，next[1]=1；
2、当判断一个字母X的next值时，需要将前一个位置的字母Y和其next值m相同的逻辑索引的字母Z进行比较，注意是Y和Z比较，并不是X；

分别有以下两种情况：

• 相同：则字母X的next值为Y的逻辑索引值+1;
• 不相同：则和Y进行下一轮比较的是和Z的next值相同的逻辑索引的字母，直到相同为止。注意：我们这里Z的next值为0，前面再无字母，则需要填写的X的next值为1；并且每一轮的比较都是Y和一个字母比较！

根据这个规律我们可以得出ababaaababaa的next数组为：

nextval数组：

1、nextval[0] = 0；

2、当判断一个字母X的nextval值时，需要先求出字符串X的next值，然后用X的next值所转化的逻辑索引值的字母Y进行比较，注意这里是X和Y比较；

分别有以下两种情况：

• 不相同：则字母X的nextval值为X的next值
• 相同：则将X与和Y的next值相同的逻辑索引的字母进行下一轮比较，直到找到不相同为止；如果最后一轮比较的next值为0，则X的nextval值为0；

根据这个规律我们可以得出ababaaababaa的nextval数组为：

如果你觉得这篇文章对您有帮助的话，麻烦帮我点个点个赞关注一下吧，创作不易，有你的支持才是我前进的动力~

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.mushiming.com/mjsbk/12911.html