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

文本编辑器中的查找替换功能,我想你应该不陌生吧?比如,我们在 Word 中把一个单词统一替换成另一个,用的就是这个功能。你有没有想过,它是怎么实现的呢?
当然,你用上一节讲的 BF 算法和 RK 算法,也可以实现这个功能,但是在某些极端情况下,BF 算法性能会退化的比较严重,而 RK 算法需要用到哈希算法,设计一个可以应对各种类型字符的哈希算法并不简单。
对于工业级的软件开发来说,我们希望算法尽可能的高效,并且在极端情况下,性能也不要退化的太严重。那么,对于查找功能是重要功能的软件来说,比如一些文本编辑器,它们的查找功能都是用哪种算法来实现的呢?有没有比 BF 算法和 RK 算法更加高效的字符串匹配算法呢?
今天,我们就来学习 BM(Boyer-Moore)算法。它是一种非常高效的字符串匹配算法,有实验统计,它的性能是著名的KMP 算法的 3 到 4 倍。BM 算法的原理很复杂,比较难懂,学起来会比较烧脑,我会尽量给你讲清楚,同时也希望你做好打硬仗的准备。好,现在我们正式开始!
BM 算法的核心思想
我们把模式串和主串的匹配过程,看作模式串在主串中不停地往后滑动。当遇到不匹配的字符时,BF 算法和 RK 算法的做法是,模式串往后滑动一位,然后从模式串的第一个字符开始重新匹配。我举个例子解释一下,你可以看我画的这幅图。
公开
同步至部落
取消
完成
0/2000
笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《数据结构与算法之美》,新⼈⾸单¥68
《数据结构与算法之美》,新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(298)
- 最新
- 精选
- SmallflyBM 算法分析着实比较复杂,不过按照老师的思路,一步一步走,看懂应该没问题的。但其实有些代码实现细节看不懂关系也不大。我们学算法主要目的是学习算法的思想,能在需要的时候加以应用就好。 但对于平时工作,几乎不可能遇到,需要自己手写一个字符串匹配算法的场景。那我们还要学,图的是什么? 我认为文章中值得学习借鉴的思想有: 1、要有优化意识,前面的 BF,RK 算法已经能够满足我们需求了,为什么发明 BM 算法?是为了减少时间复杂度,但是带来的弊端是,优化代码变得复杂,维护成本变高。 2、需要查找,需要减少时间复杂度,应该想到什么?散列表。 3、如果某个表达式计算开销比较大,又需要频繁的使用怎么办?预处理,并缓存。 (一点拙见,可能文中还有其它优秀的思想,没能 Get 到)
作者回复: 👍
17517 - 杨伟这个算法用的多么?老师为什么讲解这个算法?
作者回复: 怎么讲呢 平常不大可能会自己去实现一个bm算法 顶多就用个bf算法。不过bm算法号称最高效的 比如grep命令就是用它实现的 所以有必要讲一下 不然不完整啊 你全当思维训练吧
343 - 传说中的成大大在用一个256的数组 用字符的ascii码做下标 记录该字符出现的位置 如果存在相同字符怎么办呢?之前的会被新的覆盖掉的把!
作者回复: 是的 就是要覆盖掉 留最大的
25 - Liam好后缀原则下,最后一种情况为什么移到坏字符后面呢,不能移到好后缀的后面吗?即m+1,而不是j + 1
作者回复: 你说的对 👍 我改下
24 - P@tricK高票那个留言,是移动m位,不是m+1位。 这节课细节上小问题有点多,不过瑕不掩瑜,思想重要,细节自己钻研。
作者回复: 是的
10 - 距离对于还没毕业的我有点坚持不下去了
编辑回复: 再坚持一下
47 - cygnusgenerateGS函数里suffix和prefix的赋值应该放到while循环内,即每次k变动时都要赋值。 另外请问下:好后缀的后缀子串 b[r, m-1],这里的r的初值j+2是怎么得来的啊?
作者回复: j表示坏字符的下标 好狗追其实下标j+1
37 - seniusen好后缀原则中,最后一种情况,应该是移动 m 位吧,移动整个模式串的长度。
作者回复: 是的
5 - P@tricK老师,suffix和prefix的赋值那里有BUG,应该在每一次k的变动都要有suffix赋值。
作者回复: 是的 多谢
5 - 🐱您的好友William🐱懂了是懂了,但是你让我自己实现是不可能实现的,这辈子。。。。之后有可能实现。。。。 其实精髓都在最后那三张移动的图里,记住两原则取最大的,好后缀按“suffix”,“prefix”,“都没对上”,三个顺序输出。其中一旦在原则中出现了匹配到多次的情况,都按最保守最接近右侧的取。
作者回复: 看懂就够了 能看懂我就没白画这文章中的22张图
4
收起评论