数据结构与算法之美
王争
前 Google 工程师
280067 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 81 讲
基础篇 (38讲)
数据结构与算法之美
15
15
1.0x
00:00/00:00
登录|注册

33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?

文本编辑器中的查找替换功能,我想你应该不陌生吧?比如,我们在 Word 中把一个单词统一替换成另一个,用的就是这个功能。你有没有想过,它是怎么实现的呢?
当然,你用上一节讲的 BF 算法和 RK 算法,也可以实现这个功能,但是在某些极端情况下,BF 算法性能会退化的比较严重,而 RK 算法需要用到哈希算法,设计一个可以应对各种类型字符的哈希算法并不简单。
对于工业级的软件开发来说,我们希望算法尽可能的高效,并且在极端情况下,性能也不要退化的太严重。那么,对于查找功能是重要功能的软件来说,比如一些文本编辑器,它们的查找功能都是用哪种算法来实现的呢?有没有比 BF 算法和 RK 算法更加高效的字符串匹配算法呢?
今天,我们就来学习 BM(Boyer-Moore)算法。它是一种非常高效的字符串匹配算法,有实验统计,它的性能是著名的KMP 算法的 3 到 4 倍BM 算法的原理很复杂,比较难懂,学起来会比较烧脑,我会尽量给你讲清楚,同时也希望你做好打硬仗的准备。好,现在我们正式开始!

BM 算法的核心思想

我们把模式串和主串的匹配过程,看作模式串在主串中不停地往后滑动。当遇到不匹配的字符时,BF 算法和 RK 算法的做法是,模式串往后滑动一位,然后从模式串的第一个字符开始重新匹配。我举个例子解释一下,你可以看我画的这幅图。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《数据结构与算法之美》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(298)

  • 最新
  • 精选
  • Smallfly
    BM 算法分析着实比较复杂,不过按照老师的思路,一步一步走,看懂应该没问题的。但其实有些代码实现细节看不懂关系也不大。我们学算法主要目的是学习算法的思想,能在需要的时候加以应用就好。 但对于平时工作,几乎不可能遇到,需要自己手写一个字符串匹配算法的场景。那我们还要学,图的是什么? 我认为文章中值得学习借鉴的思想有: 1、要有优化意识,前面的 BF,RK 算法已经能够满足我们需求了,为什么发明 BM 算法?是为了减少时间复杂度,但是带来的弊端是,优化代码变得复杂,维护成本变高。 2、需要查找,需要减少时间复杂度,应该想到什么?散列表。 3、如果某个表达式计算开销比较大,又需要频繁的使用怎么办?预处理,并缓存。 (一点拙见,可能文中还有其它优秀的思想,没能 Get 到)

    作者回复: 👍

    17
    517
  • 杨伟
    这个算法用的多么?老师为什么讲解这个算法?

    作者回复: 怎么讲呢 平常不大可能会自己去实现一个bm算法 顶多就用个bf算法。不过bm算法号称最高效的 比如grep命令就是用它实现的 所以有必要讲一下 不然不完整啊 你全当思维训练吧

    3
    43
  • 传说中的成大大
    在用一个256的数组 用字符的ascii码做下标 记录该字符出现的位置 如果存在相同字符怎么办呢?之前的会被新的覆盖掉的把!

    作者回复: 是的 就是要覆盖掉 留最大的

    25
  • Liam
    好后缀原则下,最后一种情况为什么移到坏字符后面呢,不能移到好后缀的后面吗?即m+1,而不是j + 1

    作者回复: 你说的对 👍 我改下

    24
  • P@tricK
    高票那个留言,是移动m位,不是m+1位。 这节课细节上小问题有点多,不过瑕不掩瑜,思想重要,细节自己钻研。

    作者回复: 是的

    10
  • 距离
    对于还没毕业的我有点坚持不下去了

    编辑回复: 再坚持一下

    4
    7
  • cygnus
    generateGS函数里suffix和prefix的赋值应该放到while循环内,即每次k变动时都要赋值。 另外请问下:好后缀的后缀子串 b[r, m-1],这里的r的初值j+2是怎么得来的啊?

    作者回复: j表示坏字符的下标 好狗追其实下标j+1

    3
    7
  • seniusen
    好后缀原则中,最后一种情况,应该是移动 m 位吧,移动整个模式串的长度。

    作者回复: 是的

    5
  • P@tricK
    老师,suffix和prefix的赋值那里有BUG,应该在每一次k的变动都要有suffix赋值。

    作者回复: 是的 多谢

    5
  • 🐱您的好友William🐱
    懂了是懂了,但是你让我自己实现是不可能实现的,这辈子。。。。之后有可能实现。。。。 其实精髓都在最后那三张移动的图里,记住两原则取最大的,好后缀按“suffix”,“prefix”,“都没对上”,三个顺序输出。其中一旦在原则中出现了匹配到多次的情况,都按最保守最接近右侧的取。

    作者回复: 看懂就够了 能看懂我就没白画这文章中的22张图

    4
收起评论
显示
设置
留言
99+
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部