34 | 字符串匹配基础（下）：如何借助BM算法轻松理解KMP算法？
王争
该思维导图由 AI 生成，仅供参考
上一节我们讲了 BM 算法，尽管它很复杂，也不好理解，但却是工程中非常常用的一种高效字符串匹配算法。有统计说，它是最高效、最常用的字符串匹配算法。不过，在所有的字符串匹配算法里，要说最知名的一种的话，那就非 KMP 算法莫属。很多时候，提到字符串匹配，我们首先想到的就是 KMP 算法。
尽管在实际的开发中，我们几乎不大可能自己亲手实现一个 KMP 算法。但是，学习这个算法的思想，作为让你开拓眼界、锻炼下逻辑思维，也是极好的，所以我觉得有必要拿出来给你讲一讲。不过，KMP 算法是出了名的不好懂。我会尽力把它讲清楚，但是你自己也要多动动脑子。
实际上，KMP 算法跟 BM 算法的本质是一样的。上一节，我们讲了好后缀和坏字符规则，今天，我们就看下，如何借助上一节 BM 算法的讲解思路，让你能更好地理解 KMP 算法？
KMP 算法基本原理
KMP 算法是根据三位作者（D.E.Knuth，J.H.Morris 和 V.R.Pratt）的名字来命名的，算法的全称是 Knuth Morris Pratt 算法，简称为 KMP 算法。
KMP 算法的核心思想，跟上一节讲的 BM 算法非常相近。我们假设主串是 a，模式串是 b。在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，我们希望找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
KMP算法是一种高效的字符串匹配算法，通过比较BM算法和KMP算法的相似之处，以及KMP算法的基本原理和失效函数计算方法，帮助读者更好地理解KMP算法。KMP算法的核心思想是利用已匹配的好前缀信息，通过提前计算得到的next数组，实现模式串在遇到不可匹配字符时的快速滑动，从而提高匹配效率。文章详细介绍了KMP算法的基本原理和失效函数计算方法，并给出了KMP算法的框架代码和失效函数计算的代码实现。通过本文的总结，读者可以快速了解KMP算法的核心思想和实现方法，为理解和应用KMP算法打下基础。KMP算法的时间复杂度是O(m+n)，不过它的分析过程稍微需要一点技巧，不那么直观，但在实际开发中很少会有这么难分析的代码。整篇文章系统地介绍了KMP算法的原理、实现和复杂度分析，对于想深入了解字符串匹配算法的读者来说，是一篇很有价值的文章。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《数据结构与算法之美》，新⼈⾸单¥68
《数据结构与算法之美》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(221)
- 最新
- 精选
ZX最难理解的地方是 k = next[k] 因为前一个的最长串的下一个字符不与最后一个相等，需要找前一个的次长串，问题就变成了求0到next(k)的最长串，如果下个字符与最后一个不等，继续求次长串，也就是下一个next(k)，直到找到，或者完全没有作者回复: 你掌握了精髓
2018-12-1617272
李百度了下，终于搞明白了，回答自己前面一个问题。 关键是要搞明白k值是啥东西。 比如求aba 每个前缀最长可匹配前缀子串的结尾字符下标 这句话很容易引起歧义。 aba的前缀有a,ab, 后缀有ba,a 只有a与a匹配。 所以匹配的结尾下标是0. abab 显然ab和ab可以匹配，所以匹配的结尾下标是1 abaaba 下标是2 ababa 下标是2 aaaa 下标是2作者回复: 👍
2018-12-14540
feifei一个双休，加上好几个早上的时间，这两篇关于字符串匹配，弄明白了，代码我自己也实现了一遍，就论代码实现来说，KMP算法比BM算法要简单一点，这个BM算法，一个双休送给了他，慢慢的一点点理解规则，然后再一点点的，按照自己所理解的思想来实现，虽然觉得这样子慢，但能学到的会更多，要论最难理解的地方，这个ＢＭ的算法的计算next数组，这脑子绕了好久！作者回复: 我写的时候也绕了好久
2018-12-1425
P@tricK最难理解的就是kmp的next数组的这个求法了，思路本身就难，几个边界情况靠自己理清写出来没BUG更是难。 自己想到的一个简单点的解法，就是先将所有模式串的前缀子串全列出来，然后用哈希表存储，key是串，value是串长度，求解next数组值的时候将后缀子串从长到短去哈希表里找。作者回复: 👍 人才啊 不过时间复杂度就高了 后缀字串是模式串前缀的后缀子串 并不是模式串的后缀子串
2018-12-10211- suke这些对什么最长前缀后缀字符串变量的描述能不能不要加那么多形容词？用一个字符变量不就描述了么，整那么多形容词不把人搞晕才怪，自己百度一下，全明白了，相比之下，你这个描述真的是徒然增加读者的阅读障碍
作者回复: 求你退订 感激
2019-04-0227 
煦暖老师你好，第二幅图的上半部分的模式串前缀子串画错了，应该从a开始，abab，而不是baba。作者回复: 嗯嗯 多谢指正
2018-12-106- P@tricK如果 next[i-1]=k-1，也就是说，子串 b[0, k-1] 是 b[0, i-1] 的最长可匹配前缀子串。如果子串 b[0, k-1] 的下一个字符 b[k]，与 b[0, i-1] 的下一个字符 b[i] 匹配，那子串 b[0, k] 就是 b[0, i] 的最长可匹配前缀子串。所以，next[i-1] 等于 k。 --------------- 末尾应该是 next[i] 等于 k
作者回复: 嗯嗯 多谢指正
2018-12-105 
NeverMore学习啦，next数组一开始没明白，看了几次终于看懂啦。 思考了下字符串匹配，最重点的就是多移动几位，但是又不要移动过多，同时记录历史数据，以空间换时间！作者回复: 👍
2018-12-104
文祥第一个程序里面的 while (j > 0 && a[i] != b[j]) 可以改成if吧作者回复: 不可以呢
2019-03-182
Pan^yu看了三遍总算看懂了，靠@ZX的留言，然后回去在梳理才看懂作者回复: 👍
2018-12-181
收起评论
