数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?

王争 2018-12-10
上一节我们讲了 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/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(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算法,一个双休送给了他,慢慢的一点点理解规则,然后再一点点的,按照自己所理解的思想来实现,虽然觉得这样子慢,但能学到的会更多,要论最难理解的地方,这个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
收起评论
99+
返回
顶部