40｜串的朴素模式匹配算法：暴力但容易理解
王健伟
你好，我是王健伟。
前面我们在讲串的基本操作的时候，你一定发现了，我们没有提到在一个字符串中寻找子串的问题。这个寻找操作，不仅是这种数据结构中所要面对的最常见的算法，更是最重要的算法之一。这节课，我们就专门来看一看，怎么去找到这个子串。
问题的提出
对于一个串“abdecdefg”，如果希望在其中寻找“def”这个串，这个问题其实就相当于在一个主串（“abdecdefg”）中寻找一个子串（“def”）并返回该子串位置。这种子串的定位操作通常称为串的模式匹配。其中子串也被称为模式串。这里注意，因为是在主串中寻找子串，所以显然主串的长度不应该小于子串。
串的模式匹配算法有很多，比如朴素模式匹配算法（BF）、Rabin-Karp（RK）算法、KMP 算法、Boyer-Moore（BM）算法（常用于文本编辑器中，grep 命令中）等，我们会挑选两种常用的算法（BF、KMP）进行讲解。
通常来讲，我们可以通过调用前面编写的串中的 StrCmp()、SubString() 操作接口（方法）实现子串定位操作，但这节课，我们不依赖于串的任何其他操作接口来实现子串的定位操作，这里要实现的是串的朴素（简单）模式匹配算法。这个算法就是对主串的每个字符作为子串的开头与子串进行匹配。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
朴素模式匹配算法，又称为暴力匹配算法，是一种简单但常见的字符串匹配算法。该算法通过逐个字符比较主串和子串来实现子串的定位操作。尽管执行效率不高，但由于思想简单、代码实现容易，在实际应用中仍然广泛存在。 文章详细介绍了朴素模式匹配算法的实现步骤，并给出了相应的代码示例。同时，对算法的时间复杂度进行了分析，包括最好情况、最坏情况和平均情况下的时间复杂度。此外，还介绍了如何在主串中找到子串后进行替换操作，以及相应的代码实现。 通过清晰的算法描述和代码示例，读者能够快速了解朴素模式匹配算法的原理和实现方法。同时，对时间复杂度的分析也有助于读者对算法的执行效率有所了解。文章内容简洁明了，适合读者快速了解和掌握朴素模式匹配算法的基本概念和实现方式。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(1)
- 最新
- 精选
Tiger
老师您好，文章中图9后面那一段，“而后 point1 指针必须要回退“子串长度 +1”这么多的位置”，point1指针应该要回退“子串长度-2”那么多位置。2023-09-27归属地：北京
收起评论