32 | 字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？
王争
该思维导图由 AI 生成，仅供参考
从今天开始，我们来学习字符串匹配算法。字符串匹配这样一个功能，我想对于任何一个开发工程师来说，应该都不会陌生。我们用的最多的就是编程语言提供的字符串查找函数，比如 Java 中的 indexOf()，Python 中的 find() 函数等，它们底层就是依赖接下来要讲的字符串匹配算法。
字符串匹配算法很多，我会分四节来讲解。今天我会讲两种比较简单的、好理解的，它们分别是：BF 算法和 RK 算法。下一节，我会讲两种比较难理解、但更加高效的，它们是：BM 算法和 KMP 算法。
这两节讲的都是单模式串匹配的算法，也就是一个串跟一个串进行匹配。第三节、第四节，我会讲两种多模式串匹配算法，也就是在一个串中同时查找多个串，它们分别是 Trie 树和 AC 自动机。
今天讲的两个算法中，RK 算法是 BF 算法的改进，它巧妙借助了我们前面讲过的哈希算法，让匹配的效率有了很大的提升。那RK 算法是如何借助哈希算法来实现高效字符串匹配的呢？你可以带着这个问题，来学习今天的内容。
BF 算法
BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法。从名字可以看出，这种算法的字符串匹配方式很“暴力”，当然也就会比较简单、好懂，但相应的性能也不高。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
字符串匹配算法的基础知识包括朴素匹配算法（BF算法）和RK算法。BF算法通过暴力匹配方式，在主串中逐个检查子串与模式串是否匹配，时间复杂度为O(n*m)。尽管时间复杂度较高，但在实际开发中仍常用，因为大部分情况下模式串和主串长度不会太长，且算法思想简单易实现。RK算法则是BF算法的改进，利用哈希算法提升匹配效率。通过哈希算法计算子串的哈希值，RK算法的时间复杂度可降至O(n)。然而，哈希冲突可能导致时间复杂度退化为O(n*m)。文章还提到了后续将介绍的BM算法、KMP算法、Trie树和AC自动机，展示了字符串匹配算法的多样性和实用性。读者可以快速了解字符串匹配算法的基本概念和应用场景，以及RK算法如何借助哈希算法实现高效字符串匹配。RK算法的特点在于借助哈希算法提高匹配效率，但需要注意哈希冲突可能导致效率下降。文章还提到了一维字符串匹配方法，为读者提供了思考和拓展的空间。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《数据结构与算法之美》，新⼈⾸单¥68
《数据结构与算法之美》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(196)
- 最新
- 精选
ZXRK算法，在对主串构建的时候，就对比是不是一样的，一样就不继续计算后面的hash，这样会不会更快一点作者回复: 你说的很对 代码实现就是这样处理的
2018-12-0617208
✨拓星✨基于BF的匹配算法平时的用的比较多，看完之后想了一会觉得没有什么情况会用到第二种RK算法的情况，因为平时业务关系可能没有做到相关的项目，所以想问老师一般什么场景会使用RK这种匹配算法呢？作者回复: 应该是比较刁钻的场景 我也没遇到过 平时都是直接用编程语言提供的函数。不过不耽误我们学习他的思想 技巧
2018-12-06225
Spider Man老师您应该把公式的推理过程简单地说一下，这公式对您来说非常简单，但是对于我这种基础差的人，完全是懵逼的状态。看着大家讨论，却无法深入下去。/(ㄒoㄒ)/~~作者回复: 我补一下
2019-01-0920
coulson老师，前天面试被问到一个问题，关于地图算法的，比如线路推荐。请问地图算法会讲到么作者回复: 在高级篇那部分会涉及一点
2018-12-05217
Alanh[i] = 26*(h[i-1]-26^(m-1)*h[i-1]) + h[i+m-1]; 其中, h[i]、h[i-1] 分别对应 s[i] 和 s[i-1] 两个子串的哈希值 ------------------ 文中这个公式，26*(h[i-1]-26^(m-1)*h[i-1])可以化简为26*h[i-1]*(1-26^(m-1))，所以这里是不是应该改为26*(h[i-1]-26^(m-1)*s[i-1])，用s[i-1]代表当前位置的字符串的值，例如图中d的值是3，同样的公式后面加 h[i+m-1]是不是也是s[i+m-1]呢作者回复: 写错了 感谢指正 已经改了
2018-12-05216
星君好几期没看了，感觉跟不上了作者回复: 不着急 慢慢来 没必要一直紧跟着
2018-12-12211
漫漫越停看了好多天，最后还是决定继续跟随老师的脚步，为自己加油~作者回复: 停一停 歇歇挺好的 也没必要跟的很紧 搞的自己很窘迫
2018-12-187- Spider Manh[i] = 26*(h[i-1]-26^(m-1)*(s[i-1]-'a')) + (s[i+m-1]-'a'); 其中, h[i]、h[i-1] 分别对应 s[i] 和 s[i-1] 两个子串的哈希值 好吧，这一段代码我对照上下文看了10遍，看懂了。我承认我很蠢
作者回复: 抱歉 没写清楚
2019-01-095 
菜鸡程序员可不可以先不遍历所有的hash值，而是移动一位算一位hash值，然后再对比，这样能否提高效率作者回复: 可以的
2019-04-1021- 菜鸡程序员为何不再生成子串的hash值时，把hash值存到一个hashmap中，这样就不用遍历数组了，可以根据目标的hash值，直接在map的链表中查找
作者回复: 浪费空间呢
2019-04-101
收起评论
