KMP算法之NEXT数组难点分析

zzzz76 · 发表于 2016-11-12 12:22:07

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由 zzzz76 于 2016-11-12 12:42 编辑

在学习KMP算法的过程中遇到过一些难以理解的瓶颈，而之后又豁然开朗，忍不住来和大家分享一下我的理解，也算对自身知识的一种加固！

楼主学习过程中主要遇到了三个难点：
1.对next数组的理解
2.前缀回溯过程中的递归思维（most难....）
3.特殊的0

下面楼主将这三个难点串起来进行理解（借助了下老师的ppt，噶）
1.对next数组的理解

1.1.png

牢牢记住，next数组由T数组自身决定！
1.2.png

2.前缀回溯过程中的递归思维

1.3.png

将前后缀写在两个T数组里是为了后面更好的理解递归哦
1.4.png

难点来了，转换下你的思维，也就是常常遇到的自己搞自己思维
1.6.png

3.特殊的0

1.9.png

现在我们可以完善整体的理解了
2.0.png

楼主说完自己都理解了

下边是PPT和源码

游客，如果您要查看本帖隐藏内容请回复

super-M · 发表于 2016-11-13 21:15:13

理解了很久看一遍忘一遍

zzzz76 · 发表于 2016-11-13 21:24:05

super-M 发表于 2016-11-13 21:15
理解了很久看一遍忘一遍

忘一遍又理解一遍，想一想索性把它记下来：）

0洛枫0 · 发表于 2016-12-2 08:33:18

学习

L丶 · 发表于 2016-12-5 14:46:01

好深奥啊

流月飞星 · 发表于 2016-12-6 10:35:56

0洛枫0 · 发表于 2016-12-8 08:48:25

学习

1134940721小林 · 发表于 2017-7-13 13:47:35

ene

weisuo · 发表于 2017-8-8 20:38:25

吃瓜c与数据 · 发表于 2017-9-14 14:20:57

拿奖励去学习

cyndiwants · 发表于 2017-9-16 11:15:04

谢谢楼主大大分享喽，嘿嘿😁

Code_mzh · 发表于 2018-2-1 21:22:47

这个很不错啊

asiya33 · 发表于 2018-2-8 22:58:14

谢谢，刚刚学习

xiaoxiaoshaonia · 发表于 2018-2-14 11:40:09

感谢分享

我要去实习！ · 发表于 2018-3-25 19:10:01

lnking · 发表于 2018-3-26 15:05:05

mark

cagescott · 发表于 2018-5-29 12:37:18

拿源码，回去试试

447908543 · 发表于 2019-4-9 01:07:12

很棒的解析，感谢楼主

文浪浪浪 · 发表于 2019-4-19 10:02:20

撂爪就忘

DenieceYT · 发表于 2020-3-25 20:53:11

我想看源码😃

账号		自动登录	找回密码
密码			立即注册

[技术交流] KMP算法之NEXT数组难点分析

马上注册，结交更多好友，享用更多功能^_^

回帖奖励 +1 鱼币

回帖奖励 +1 鱼币

回帖奖励 +1 鱼币

回帖奖励 +1 鱼币

回帖奖励 +1 鱼币

回帖奖励 +1 鱼币

回帖奖励 +1 鱼币

回帖奖励 +1 鱼币