5.4 正则表达式
Robert Sedgewick Kevin Wayne
在许多应用程序中,我们在查找子字符串时并没有被查找模式的完整信息。文本编辑器的用户可能希望仅指定模式的一部分,或是指定某种能够匹配若干个不同单词的模式,或是指定几种可以任意匹配的不同模式。例如,生物学家可能希望在基因组序列中寻找满足特定条件的基因。本节中,我们将会学习如何高效地完成这种类型的模式匹配。
5.3 节中的算法完全依赖指定完整的模式字符串,因此需要寻找不同的方法。本节将会学习的一些基本工具能够构造一个非常强大的字符串查找程序,它能够在长度为
的文本中匹配长度为
的复杂模式。在最坏情况下,它所需的时间和
成正比,而在一般的应用程序中还会快得多。
![](https://static001.geekbang.org/files/resource/ebook/100010/image00798.gif)
![](https://static001.geekbang.org/files/resource/ebook/100010/image00801.gif)
![](https://static001.geekbang.org/files/resource/ebook/100010/image01090.gif)
首先,我们需要一种描述模式的方法,即一种严谨的说明上述“部分子字符串的查找问题”的方式。这份说明必须含有一些比 5.3 节中使用的“检查文本字符串的第 i 个字符和模式字符串的第 j 个字符是否匹配”更加强大的原始操作。为此,我们使用正则表达式。它能够用自然、简单而强大的 3 种操作组合来描述模式。
程序员使用正则表达式的历史已经有数十年了。随着网络搜索的爆炸性增长,它们的使用变得更加广泛。本节开始会讨论几个应用程序。这不仅是为了让你感受它的用途和功能,也是为了让你对它的基本性质更加熟悉。
公开
同步至部落
取消
完成
0/2000
笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
![](https://static001.geekbang.org/resource/image/d0/e4/d0880927e2a522a038be2d04bf19dfe4.png)
本文深入介绍了正则表达式在字符串匹配中的重要性和应用。正则表达式作为一种强大的描述模式的工具,通过连接、或、闭包等基本操作,能够描述复杂的字符串匹配规则。文章详细介绍了正则表达式的语法和语义,以及它们在字符串匹配中的应用。通过举例和定义,读者可以快速了解正则表达式的基本操作和在字符串匹配中的应用,以及它们在计算机科学中的重要性。 文章还指出,正则表达式的应用与计算机科学中的基础问题有着紧密的联系,例如与算法的相似性和非确定性的关系。此外,正则表达式在实际应用中具有广泛的用途,包括子字符串查找、合法性检查、以及作为程序员的工具箱中的重要工具。正则表达式的简洁性和高效性使得它成为处理字符串匹配问题的重要工具,而且已经被内置于许多现代编程系统之中。 文章还介绍了正则表达式与非确定有限状态自动机的关系,以及其在模式匹配中的应用,为读者提供了深入的技术内容和实际应用示例。通过模拟 NFA 的运行和构造与正则表达式对应的 NFA,读者可以更好地理解正则表达式在实际应用中的运行机制和性能特点。 总之,本文全面介绍了正则表达式的基本操作和在字符串匹配中的应用,以及它们在计算机科学中的重要性,对于读者快速了解和掌握正则表达式的应用具有重要意义。文章内容丰富,涵盖了技术细节和实际应用,适合对正则表达式感兴趣的读者阅读学习。
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《算法(第 4 版)》
《算法(第 4 版)》
立即购买
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示,欢迎踊跃留言。
收起评论