34 | 字符串匹配基础（下）：如何借助BM算法轻松理解KMP算法？

Dec 10, 2018

34 | 字符串匹配基础（下）：如何借助BM算法轻松理解KMP算法？-极客时间



下载APP





关闭

讲堂部落提薪训练营云原生训练营架构实战营企业版极客商城兑换中心 App下载浏览器插件

渠道合作

推荐作者

34 | 字符串匹配基础（下）：如何借助BM算法轻松理解KMP算法？

2018-12-10 王争来自北京

《数据结构与算法之美》

课程介绍



讲述：冯永吉

时长11:56大小10.90M



上一节我们讲了 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。在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，我们希望找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况。
还记得我们上一节讲到的好后缀和坏字符吗？这里我们可以类比一下，在模式串和主串匹配的过程中，把不能匹配的那个字符仍然叫作坏字符，把已经匹配的那段字符串叫作好前缀。
当遇到坏字符的时候，我们就要把模式串往后滑动，在滑动的过程中，只要模式串和好前缀有上下重合，前面几个字符的比较，就相当于拿好前缀的后缀子串，跟模式串的前缀子串在比较。这个比较的过程能否更高效了呢？可以不用一个字符一个字符地比较了吗？
KMP 算法就是在试图寻找一种规律：在模式串和主串匹配的过程中，当遇到坏字符后，对于已经比对过的好前缀，能否找到一种规律，将模式串一次性滑动很多位？
我们只需要拿好前缀本身，在它的后缀子串中，查找最长的那个可以跟好前缀的前缀子串匹配的。假设最长的可匹配的那部分前缀子串是{v}，长度是 k。我们把模式串一次性往后滑动 j-k 位，相当于，每次遇到坏字符的时候，我们就把 j 更新为 k，i 不变，然后继续比较。
为了表述起来方便，我把好前缀的所有后缀子串中，最长的可匹配前缀子串的那个后缀子串，叫作最长可匹配后缀子串；对应的前缀子串，叫作最长可匹配前缀子串。
如何来求好前缀的最长可匹配前缀和后缀子串呢？我发现，这个问题其实不涉及主串，只需要通过模式串本身就能求解。所以，我就在想，能不能事先预处理计算好，在模式串和主串匹配的过程中，直接拿过来就用呢？
类似 BM 算法中的 bc、suffix、prefix 数组，KMP 算法也可以提前构建一个数组，用来存储模式串中每个前缀（这些前缀都有可能是好前缀）的最长可匹配前缀子串的结尾字符下标。我们把这个数组定义为 next 数组，很多书中还给这个数组起了一个名字，叫失效函数（failure function）。
数组的下标是每个前缀结尾字符下标，数组的值是这个前缀的最长可以匹配前缀子串的结尾字符下标。这句话有点拗口，我举了一个例子，你一看应该就懂了。
有了 next 数组，我们很容易就可以实现 KMP 算法了。我先假设 next 数组已经计算好了，先给出 KMP 算法的框架代码。
// a, b分别是主串和模式串；n, m分别是主串和模式串的长度。
public static int kmp(char[] a, int n, char[] b, int m) {
  int[] next = getNexts(b, m);
  int j = 0;
  for (int i = 0; i < n; ++i) {
    while (j > 0 && a[i] != b[j]) { // 一直找到a[i]和b[j]
      j = next[j - 1] + 1;
    }
    if (a[i] == b[j]) {
      ++j;
    }
    if (j == m) { // 找到匹配模式串的了
      return i - m + 1;
    }
  }
  return -1;
}
失效函数计算方法KMP 算法的基本原理讲完了，我们现在来看最复杂的部分，也就是 next 数组是如何计算出来的？
当然，我们可以用非常笨的方法，比如要计算下面这个模式串 b 的 next[4]，我们就把 b[0, 4]的所有后缀子串，从长到短找出来，依次看看，是否能跟模式串的前缀子串匹配。很显然，这个方法也可以计算得到 next 数组，但是效率非常低。有没有更加高效的方法呢？
这里的处理非常有技巧，类似于动态规划。不过，动态规划我们在后面才会讲到，所以，我这里换种方法解释，也能让你听懂。
我们按照下标从小到大，依次计算 next 数组的值。当我们要计算 next[i]的时候，前面的 next[0]，next[1]，……，next[i-1]应该已经计算出来了。利用已经计算出来的 next 值，我们是否可以快速推导出 next[i]的值呢？
如果 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]等于 k。但是，如果 b[0, k-1]的下一字符 b[k]跟 b[0, i-1]的下一个字符 b[i]不相等呢？这个时候就不能简单地通过 next[i-1]得到 next[i]了。这个时候该怎么办呢？
我们假设 b[0, i]的最长可匹配后缀子串是 b[r, i]。如果我们把最后一个字符去掉，那 b[r, i-1]肯定是 b[0, i-1]的可匹配后缀子串，但不一定是最长可匹配后缀子串。所以，既然 b[0, i-1]最长可匹配后缀子串对应的模式串的前缀子串的下一个字符并不等于 b[i]，那么我们就可以考察 b[0, i-1]的次长可匹配后缀子串 b[x, i-1]对应的可匹配前缀子串 b[0, i-1-x]的下一个字符 b[i-x]是否等于 b[i]。如果等于，那 b[x, i]就是 b[0, i]的最长可匹配后缀子串。
可是，如何求得 b[0, i-1]的次长可匹配后缀子串呢？次长可匹配后缀子串肯定被包含在最长可匹配后缀子串中，而最长可匹配后缀子串又对应最长可匹配前缀子串 b[0, y]。于是，查找 b[0, i-1]的次长可匹配后缀子串，这个问题就变成，查找 b[0, y]的最长匹配后缀子串的问题了。
按照这个思路，我们可以考察完所有的 b[0, i-1]的可匹配后缀子串 b[y, i-1]，直到找到一个可匹配的后缀子串，它对应的前缀子串的下一个字符等于 b[i]，那这个 b[y, i]就是 b[0, i]的最长可匹配后缀子串。
前面我已经给出 KMP 算法的框架代码了，现在我把这部分的代码也写出来了。这两部分代码合在一起，就是整个 KMP 算法的代码实现。
// b表示模式串，m表示模式串的长度
private static int[] getNexts(char[] b, int m) {
  int[] next = new int[m];
  next[0] = -1;
  int k = -1;
  for (int i = 1; i < m; ++i) {
    while (k != -1 && b[k + 1] != b[i]) {
      k = next[k];
    }
    if (b[k + 1] == b[i]) {
      ++k;
    }
    next[i] = k;
  }
  return next;
}
KMP 算法复杂度分析KMP 算法的原理和实现我们就讲完了，我们现在来分析一下 KMP 算法的时间、空间复杂度是多少？
空间复杂度很容易分析，KMP 算法只需要一个额外的 next 数组，数组的大小跟模式串相同。所以空间复杂度是 O(m)，m 表示模式串的长度。
KMP 算法包含两部分，第一部分是构建 next 数组，第二部分才是借助 next 数组匹配。所以，关于时间复杂度，我们要分别从这两部分来分析。
我们先来分析第一部分的时间复杂度。
计算 next 数组的代码中，第一层 for 循环中 i 从 1 到 m-1，也就是说，内部的代码被执行了 m-1 次。for 循环内部代码有一个 while 循环，如果我们能知道每次 for 循环、while 循环平均执行的次数，假设是 k，那时间复杂度就是 O(k*m)。但是，while 循环执行的次数不怎么好统计，所以我们放弃这种分析方法。
我们可以找一些参照变量，i 和 k。i 从 1 开始一直增加到 m，而 k 并不是每次 for 循环都会增加，所以，k 累积增加的值肯定小于 m。而 while 循环里 k=next[k]，实际上是在减小 k 的值，k 累积都没有增加超过 m，所以 while 循环里面 k=next[k]总的执行次数也不可能超过 m。因此，next 数组计算的时间复杂度是 O(m)。
我们再来分析第二部分的时间复杂度。分析的方法是类似的。
i 从 0 循环增长到 n-1，j 的增长量不可能超过 i，所以肯定小于 n。而 while 循环中的那条语句 j=next[j-1]+1，不会让 j 增长的，那有没有可能让 j 不变呢？也没有可能。因为 next[j-1]的值肯定小于 j-1，所以 while 循环中的这条语句实际上也是在让 j 的值减少。而 j 总共增长的量都不会超过 n，那减少的量也不可能超过 n，所以 while 循环中的这条语句总的执行次数也不会超过 n，所以这部分的时间复杂度是 O(n)。
所以，综合两部分的时间复杂度，KMP 算法的时间复杂度就是 O(m+n)。
解答开篇 & 内容小结KMP 算法讲完了，不知道你理解了没有？如果没有，建议多看几遍，自己多思考思考。KMP 算法和上一节讲的 BM 算法的本质非常类似，都是根据规律在遇到坏字符的时候，把模式串往后多滑动几位。
BM 算法有两个规则，坏字符和好后缀。KMP 算法借鉴 BM 算法的思想，可以总结成好前缀规则。这里面最难懂的就是 next 数组的计算。如果用最笨的方法来计算，确实不难，但是效率会比较低。所以，我讲了一种类似动态规划的方法，按照下标 i 从小到大，依次计算 next[i]，并且 next[i]的计算通过前面已经计算出来的 next[0]，next[1]，……，next[i-1]来推导。
KMP 算法的时间复杂度是 O(n+m)，不过它的分析过程稍微需要一点技巧，不那么直观，你只要看懂就好了，并不需要掌握，在我们平常的开发中，很少会有这么难分析的代码。
课后思考至此，我们把经典的单模式串匹配算法全部讲完了，它们分别是 BF 算法、RK 算法、BM 算法和 KMP 算法，关于这些算法，你觉得什么地方最难理解呢？
欢迎留言和我分享，也欢迎点击“请朋友读”，把今天的内容分享给你的好友，和他一起讨论、学习。

分享给需要的人，Ta购买本课程，你将得20元

生成海报并分享

赞 59

提建议

33 | 字符串匹配基础（中）：如何实现文本编辑器中的查找功能？

35 | Trie树：如何实现搜索引擎的搜索关键词提示功能？

 写留言

精选留言(215)

ZX
2018-12-16
最难理解的地方是 k = next[k] 因为前一个的最长串的下一个字符不与最后一个相等，需要找前一个的次长串，问题就变成了求0到next(k)的最长串，如果下个字符与最后一个不等，继续求次长串，也就是下一个next(k)，直到找到，或者完全没有
作者回复: 你掌握了精髓
共 16 条评论
263
他在她城断了弦
2018-12-15
关于求next数组这部分写的太不好懂了，建议作者别用太多长句，切换成短句，方便大家理解。。
共 7 条评论
103
algo
2019-01-19
推荐读者先去看下这篇文章，然后再来看看，理解next会比较有帮助。 https://www.zhihu.com/question/21923021，逍遥行的回答
共 6 条评论
75
李
2018-12-14
终于看明白了，感觉设置了很多干扰项。其实用迭代思想解释就能理解了。这个算法本质是找相等的最长匹配前缀和最长匹配后缀。有两种情况，（1）如果b[i-1]的最长前缀下一个字符与b[i]相等，则next[i]=next[i-1]+1. （2）如果不相等，则我们假设找到b[i-1]的最长前缀里有b[0,y]与后缀的子串b[z,i-1]相等，然后只要b[y+1]与b[i]相等，那么b[0,y+1]就是最长匹配前缀。这个y可以不断的通过迭代缩小就可以找到
展开
共 3 条评论
75
slvher
2018-12-19
「我们假设 b[0, i] 的最长可匹配后缀子串是 b[r, i]。如果我们把最后一个字符去掉，那 b[r, i-1] 肯定是 b[0, i-1] 的可匹配后缀子串，但不一定是最长可匹配后缀子串。」 ========= 手动分割线 ======== 对文中这句话，我的理解如下：因为 b[i] 的约束可能导致 r 靠近 i，故去掉 b[i] 字符后，b[r, i-1] 虽然肯定是 b[0, i-1] 的可匹配后缀子串，但不一定是其中最长的。例如：设模式串好前缀为 "abxabcabxabx"，其最长可匹配后缀子串为 "abx"，去掉最后的字符 'x' 后，虽然 "ab" 还是好前缀的可匹配后缀子串，但 "abxab" 才是最长可匹配后缀子串。这句话虽然本身逻辑上是正确的，与上下文逻辑衔接性不强，感觉去掉这句更有利于对 next 数组第二种情况的理解。
展开
共 6 条评论
56
李
2018-12-14
百度了下，终于搞明白了，回答自己前面一个问题。关键是要搞明白k值是啥东西。比如求aba 每个前缀最长可匹配前缀子串的结尾字符下标这句话很容易引起歧义。 aba的前缀有a,ab, 后缀有ba,a 只有a与a匹配。所以匹配的结尾下标是0. abab 显然ab和ab可以匹配，所以匹配的结尾下标是1 abaaba 下标是2 ababa 下标是2 aaaa 下标是2
展开
作者回复: 👍
共 5 条评论
38
niulixin
2018-12-16
我觉得bm算法倒是好理解但是kmp的算法的next数组我感觉不太好理解啊
共 2 条评论
35
Flash
2019-02-16
最难理解的是KMP算法了。总体上，KMP算法是借鉴了BM算法本质思想的，都是遇到坏字符的时候，把模式串往后多滑动几位。 1.但是这里要注意一个细节，不然容易被前面学的BM算法给误导，导致难以理解。 BM算法是对模式串从后往前比较，每次是将主串的下标 ”i“ 往后移动多位。(这符合我们正常的思维，所以好理解) KMP虽然也是往后移动多位，但是比较时，是对模式串从前往后比较；对于主串已经比较过的部分，保持主串的 ”i“ 指针(即下标)不回溯。而是通过修改模式串的”j“指针，变相地让模式串移动到有效的位置。(这里修改"j"，是让"j"变小了，我们说的还是将模式串往后移动，所以不太好理解) 2.KMP算法中不好难理解的，构建next数组，其实很简单，要多下自己的脑筋，不要被带偏了，就好理解了。就是求next[i](动态规划的思想，根据前面已经计算好的结果next[0]...next[i-1]来得到next[i])，前一个的最长串的下一个字符与最后一个相等，那next[i]就=next[i-1]+1；否则就需要找前一个的次长串，递归这个过程，直到找到或没有。
展开
共 1 条评论
23
feifei
2018-12-14
一个双休，加上好几个早上的时间，这两篇关于字符串匹配，弄明白了，代码我自己也实现了一遍，就论代码实现来说，KMP算法比BM算法要简单一点，这个BM算法，一个双休送给了他，慢慢的一点点理解规则，然后再一点点的，按照自己所理解的思想来实现，虽然觉得这样子慢，但能学到的会更多，要论最难理解的地方，这个ＢＭ的算法的计算next数组，这脑子绕了好久！
作者回复: 我写的时候也绕了好久
23
Smallfly
2018-12-11
「那 b[r, i-1] 肯定是 b[0, i-1] 的可匹配后缀子串，但并不一定是最长可匹配后缀子串。」后半句不是很理解，如果模式串是 b[0, i-1]，i-1 已经是最后一个字符了，那么为什么 b[r, i-1] 不一定是 b[0, i-1] 的最长可匹配后缀子串呢？
共 1 条评论
19
饺子
2019-02-25
😂😂😂讲移动那幅图是不是写错了 j=j-k 不应该是j=k嘛
共 6 条评论
17
luo
2019-01-10
3遍才理解了差不多，还有一句话之前留言的还是木有理解，BM是去滑动主串，KMP是利用模式串的好前缀规则去跳过模式串（相当于滑动模式串）主串递增的形式。最难理解的就是next数组中的求解，如果b[0,i-1]的最长前缀是k-1 那b[0,k-1]就是最长的前缀这里开始分两种情况，第一种情况：b[0,k-1]的下一个字符b[k]=b[i],则最长前缀子串就变成b[0,k]，最长后缀就变成b[i-k,i]。next[i]=next[i-1]+1 第二种情况：b[0,k-1]的下一个字符b[k]≠b[i]，这时候我们要去寻找的就是b[0,i-1]中的最长前缀子串（最长匹配前后缀子串b[0,y] 和b[i-y-1,i-1]这两本身就是一一匹配的，而next数组记录的只有前缀我们仍然利用现有条件做推断）的最长可匹配前缀子串（必然跟后缀子串一致），就是b[0,i-1]的次长可匹配子串（划重点）（因为b[0,i-1]的最长可匹配子串c因为c这个串接下来一个字符跟b[i]不等，求取c它的最长可匹配子串一直到下个字符b[x+1]与b[i]相等递归求取）。可能我说的跟理解的有点问题，举个例子： abeabfabeabe(主串) abeabfabeabc（模型串）到e处不能匹配，最长可匹配子串就是 abeab接下来发现f与e不一致然后再求取abeab的最长可匹配子串，为ab接下去的e刚好跟e匹配。
展开
12
P@tricK
2018-12-10
最难理解的就是kmp的next数组的这个求法了，思路本身就难，几个边界情况靠自己理清写出来没BUG更是难。自己想到的一个简单点的解法，就是先将所有模式串的前缀子串全列出来，然后用哈希表存储，key是串，value是串长度，求解next数组值的时候将后缀子串从长到短去哈希表里找。
作者回复: 👍 人才啊不过时间复杂度就高了后缀字串是模式串前缀的后缀子串并不是模式串的后缀子串
共 2 条评论
11
不上进的码农
2018-12-10
厉害厉害，这个算法的精髓是不是就是求next数组啊，还有BM算法中的应该也是求那两个数组。我觉着应该理一理这两种求数组的过程，这求数组的过程是不是也是一个特别好的算法呀！
8
AlexS
2019-12-04
来来来，KMP框架代码都没看懂的同学看这里看这里。 i：始终是主串的下标。 j：始终是模式串的下标。关键点是，在匹配过程中的任何时候，主串下标为 i 的字符永远和模式串下标为 j 的字符对齐。例如，从初始状态开始，i 一直在增加，而 j 保持为0 （没有任何字符匹配上），那么它的含义就是模式串向后移动了 i 位。同时因为j=0，所以此时模式串首和主串 i 下标对齐。
展开
共 2 条评论
7
Stephen
2018-12-13
看了好几天，终于搞懂了
7
Kevin
2018-12-27
时间复杂度那个while增长量是怎么推敲出整体小于m或者n的，有点不大理解
6
徐亮
2019-09-23
这两节课难啃啊
共 3 条评论
5
suke
2019-04-02
这些对什么最长前缀后缀字符串变量的描述能不能不要加那么多形容词？用一个字符变量不就描述了么，整那么多形容词不把人搞晕才怪，自己百度一下，全明白了，相比之下，你这个描述真的是徒然增加读者的阅读障碍
作者回复: 求你退订感激
共 2 条评论
5
煦暖
2018-12-10
老师你好，第二幅图的上半部分的模式串前缀子串画错了，应该从a开始，abab，而不是baba。
作者回复: 嗯嗯多谢指正
5

