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

精选留言(137)

• 

  ZX

  最难理解的地方是
  k = next[k]
  因为前一个的最长串的下一个字符不与最后一个相等，需要找前一个的次长串，问题就变成了求0到next(k)的最长串，如果下个字符与最后一个不等，继续求次长串，也就是下一个next(k)，直到找到，或者完全没有
  

  作者回复: 你掌握了精髓

  2018-12-16

   3

   99
• 

  他在她城断了弦

  关于求next数组这部分写的太不好懂了，建议作者别用太多长句，切换成短句，方便大家理解。。

  2018-12-15

  

   44
• 

  slvher

  「我们假设 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 数组第二种情况的理解。

  2018-12-19

   1

   33
• 

  Alpha.

  推荐读者先去看下这篇文章，然后再来看看，理解next会比较有帮助。
  https://www.zhihu.com/question/21923021，逍遥行 的回答

  2019-01-19

   1

   22
• 

  Smallfly

  「那 b[r, i-1] 肯定是 b[0, i-1] 的可匹配后缀子串，但并不一定是最长可匹配后缀子串。」后半句不是很理解，如果模式串是 b[0, i-1]，i-1 已经是最后一个字符了，那么为什么 b[r, i-1] 不一定是 b[0, i-1] 的最长可匹配后缀子串呢？
  

  2018-12-11

  

   18
• 

  Niulx

  我觉得bm算法倒是好理解但是kmp的算法的next数组我感觉不太好理解啊

  2018-12-16

  

   15
• 

  李

  终于看明白了，感觉设置了很多干扰项。其实用迭代思想解释就能理解了。
  这个算法本质是找相等的最长匹配前缀和最长匹配后缀。
  有两种情况，
  （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可以不断的通过迭代缩小就可以找到
  

  2018-12-14

  

   13
• 

  feifei

  一个双休，加上好几个早上的时间，这两篇关于字符串匹配，弄明白了，代码我自己也实现了一遍，就论代码实现来说，KMP算法比BM算法要简单一点，这个BM算法，一个双休送给了他，慢慢的一点点理解规则，然后再一点点的，按照自己所理解的思想来实现，虽然觉得这样子慢，但能学到的会更多，要论最难理解的地方，这个ＢＭ的算法的计算next数组，这脑子绕了好久！

  作者回复: 我写的时候也绕了好久

  2018-12-14

  

   12
• 

  李

  百度了下，终于搞明白了，回答自己前面一个问题。
  关键是要搞明白k值是啥东西。
  比如求aba 每个前缀最长可匹配前缀子串的结尾字符下标
  这句话很容易引起歧义。
  aba的前缀有a,ab, 后缀有ba,a 只有a与a匹配。 所以匹配的结尾下标是0.
  abab 显然ab和ab可以匹配，所以匹配的结尾下标是1
  abaaba 下标是2
  ababa 下标是2
  aaaa 下标是2
  
  
  
  
  

  作者回复: 👍

  2018-12-14

   1

   10
• 

  Flash

  
  最难理解的是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；否则就需要找前一个的次长串，递归这个过程，直到找到或没有。

  2019-02-16

  

   8
• 

  不上进的码农

  厉害厉害，这个算法的精髓是不是就是求next数组啊，还有BM算法中的应该也是求那两个数组。我觉着应该理一理这两种求数组的过程，这求数组的过程是不是也是一个特别好的算法呀！

  2018-12-10

  

   6
• 

  饺子

  😂😂😂讲移动那幅图是不是写错了 j=j-k
  不应该是j=k嘛

  2019-02-25

   2

   5
• 

  luo

  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匹配。

  2019-01-10

  

   5
• 

  Kevin

  时间复杂度那个while增长量是怎么推敲出整体小于m或者n的，有点不大理解

  2018-12-27

  

   5
• 

  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-10

  

   5
• 

  煦暖

  老师你好，第二幅图的上半部分的模式串前缀子串画错了，应该从a开始，abab，而不是baba。

  作者回复: 嗯嗯 多谢指正

  2018-12-10

  

   4
• 

  Stephen

  看了好几天，终于搞懂了

  2018-12-13

  

   3
• 

  P@tricK

  最难理解的就是kmp的next数组的这个求法了，思路本身就难，几个边界情况靠自己理清写出来没BUG更是难。
  自己想到的一个简单点的解法，就是先将所有模式串的前缀子串全列出来，然后用哈希表存储，key是串，value是串长度，求解next数组值的时候将后缀子串从长到短去哈希表里找。

  作者回复: 👍 人才啊 不过时间复杂度就高了 后缀字串是模式串前缀的后缀子串 并不是模式串的后缀子串

  2018-12-10

   1

   3
• 

  李

  那 b[r, i-1] 肯定是 b[0, i-1] 的可匹配后缀子串，但并不一定是最长可匹配后缀子串。
  我研究了一会，这句话有误，建议更正。这里应该说一定就是最长可匹配字符串。
  假设不是最长的，那b[r-1]就应该有匹配相等的，这显然矛盾

  2018-12-14

  

   2
• 

  walor

  可是，如何求得 b[0, i-1] 的次长可匹配后缀子串呢？次长可匹配后缀子串肯定被包含在最长可匹配后缀子串中，而最长可匹配后缀子串又对应最长可匹配前缀子串 b[0, y]。于是，查找 b[0, i-1] 的次长可匹配后缀子串，这个问题就变成，查找 b[0, y] 的最长匹配后缀子串的问题了。
  
  @争哥 怎么就转换为 b[0, y] 的最长匹配后缀子串了？

  2018-12-10

   1

   2