数据结构KMP-NEXT数组计算方法
5星 · 超过95%的资源 需积分: 33 172 浏览量
2012-03-25
15:52:55
上传
评论 1
收藏 26KB DOC 举报 
详解 KMP 算法中 Next 数组的求法
例如：
1 2 3 4 5 6 7 8
模式串 a b a a b c a c
next 值 0 1 1 2 2 3 1 2
next 数组的求解方法是：第一位的 next 值为 0，第二位的 next 值
为 1，后面求解每一位的 next 值时，根据前一位进行比较。首先将
前一位与其 next 值对应的内容进行比较，如果相等，则该位的 next
值就是前一位的 next 值加上 1；如果不等，向前继续寻找 next 值对
应的内容来与前一位进行比较，直到找到某个位上内容的 next 值对
应的内容与前一位相等为止，则这个位对应的值加上 1 即为需求的
next 值；如果找到第一位都没有找到与前一位相等的内容，那么需
求的位上的 next 值即为 1。
看起来很令人费解，利用上面的例子具体运算一遍。
1.前两位必定为 0 和 1。
2.计算第三位的时候，看第二位 b 的 next 值，为 1，则把 b 和 1
对应的 a 进行比较，不同，则第三位 a 的 next 的值为 1，因为一直比
到最前一位，都没有发生比较相同的现象。
3.计算第四位的时候，看第三位 a 的 next 值，为 1，则把 a 和 1
对应的 a 进行比较，相同，则第四位 a 的 next 的值为第三位 a 的
next 值加上 1。为 2。因为是在第三位实现了其 next 值对应的值与第
三位的值相同。
资源评论
大师兄在取经2013-01-09挺不错的，不过我们书本初始是“-1”。其实都一样，谢了
