数据结构KMP-NEXT数组计算方法_数据结构中next数组怎么求资源-CSDN文库

5星 · 超过95%的资源需积分: 33 184 浏览量 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 值对应的值与第

三位的值相同。

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余1页未读，立即下载

内容反馈

大师兄在取经

2013-01-09

挺不错的，不过我们书本初始是“-1”。其实都一样，谢了

kingoverliu

粉丝: 2
资源: 22

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip