KMP字符串匹配

模型算法

首先我觉得有必要提及三位老人家的名字：Knuth-Morris-Pratt

KMP 这个算法思路一直研究了1天半才弄明白，大话数据结构里面程杰老师那个有些生涩难懂，没消化得了，但我主看的是他的书，后来辗转看了几篇帖子也是没有理解，为啥上来直接就是next数组，直到看了小甲鱼数据结构的视频，小甲鱼老师的3个启示我算是开了窍理解为什么需要next数组，回头看完阮一峰老师的博客算是透彻理解了KMP,看毛片算法是第一个让我烧脑思考的算法，郁闷了一天终于有了一些眉目，但是为什么用前缀数组：next数组，为什么可行，还没弄明白

• 小甲鱼的三个启示欠缺，带来一些新的思路，开始有了新的思维方向
  http://blog.fishc.com/2274.html

• 阮一峰老师算是带我进来kmp的大门，弄清楚kmp的匹配过程
  http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

• 这里借鉴阮老师思路，也给出了代码
  http://www.61mon.com/index.php/archives/183/

• 自己推理了next数组
  http://blog.fishc.com/2297.html

• 又看了一遍大话数据结构那里推理了 nextval数组

• next数组也就是前缀数组的进一步理解
  http://www.cnblogs.com/yjiyjige/p/3263858.html

• next数组
  http://liam0205.me/2016/12/20/KMP-Algorithm/

• 看完这个视频有了解到了一个新的高度
  https://www.youtube.com/watch?v=GTJr8OvyEVQ

• 关联：AC自动机
  http://www.cndv.org/post-4.html
  https://zh.wikipedia.org/wiki/AC%E8%87%AA%E5%8A%A8%E6%9C%BA%E7%AE%97%E6%B3%95

• 代码部分欠缺