UC知道模式串t=‘abcaabbabcab’,求next[j] nextval[j]的值
来源：百度知道 编辑：UC知道 时间：2024/05/14 10:02:35
已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。
j 1 2 3 4 5 6 7 8 9 10 11 12
t串 a b c a a b b a b c a b
next[j] 0 1 1 1 2 2 3 1 2 3 4 5
nextval[j] 0 1 1 0 2 1 3 0 1 1 0 5
怎么算的？实在看不懂。希望写的通俗点，这题只是填空题，求next和nextval函数值。
j 1 2 3 4 5 6 7 8 9 10 11 12
t串 a b c a a b b a b c a b
next[j] 0 1 1 1 2 2 3 1 2 3 4 5
nextval[j] 0 1 1 0 2 1 3 0 1 1 0 5
怎么算的？实在看不懂。希望写的通俗点，这题只是填空题，求next和nextval函数值。
求第j个字母的next值时，看它前边一个字符往前数的最长字串是否与从第一个开始的相同，如果相同则为长度+1.
比如第5个字母为a,它前边的字串为abca，那么因为从第4个字母往前数最长与第一个往后数相同的子串为1，即是a，所以next值为2.
第7个字母为b,它前边的字串为abcaab，那么因为从第6个字符开始往前数最长与从第一个字符往后数相同的子串为2，即为ab，所以next值为3.
实在不行就把代码背过，往里凑结果呵呵，感觉讲的很清楚了。
http://v.youku.com/v_show/id_XOTI3MTY2OTI=.html
推荐看看这个，严蔚敏老师讲的