详解 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 值对应的值与第
三位的值相同。
kingoverliu
- 粉丝: 2
- 资源: 23
我的内容管理
收起
- 我的资源
快来上传第一个资源
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助
会员权益专享
最新资源
- ARM Cortex-A(armV7)编程手册V4.0.pdf
- ABB机器人保养总结解析.ppt
- 【超详细图解】菜鸡如何理解双向链表的python代码实现
- 常用网络命令的使用 ipconfig ping ARP FTP Netstat Route Tftp Tracert Telnet nslookup
- 基于单片机控制的DC-DC变换电路
- RS-232接口电路的ESD保护.pdf
- linux下用time(NULL)函数和localtime()获取当前时间的方法
- Openstack用户使用手册.docx
- KUKA KR 30 hA,KR 60 hA机器人产品手册.pdf
- Java programming with JNI
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论1