KMP

首先，列出一些我参考的教程，我都读过之后认为阮一峰和王超的教学是最简洁的

• 孤~影的博客园文章

• geeks-for-geeks

• 阮一峰的博客

• 王超的个人博客

• jihite的C实现

心得

基本上每一篇讲KMP的都是从相同的“暴力算法”出发的，KMP的算法比起暴力算法最大的优势就是通过“next数组”计算query本身的重复性，找到上一次失去匹配的位置，从上次失去匹配的位置开始下一次匹配。KMP利用这个信息减少了一些计算量的浪费。

其实如果query没有重复，KMP算法的效率和“暴力算法”相等

extended KMP

收藏一些教学帖子，先挖坑，有空学一下

• 博客园

• programmersought