算法(第 4 版)
Robert Sedgewick, Kevin Wayne
ACM Fellow, ACM 杰出教育家
2178 人已学习
立即订阅
登录后,你可以任选4讲全文学习
推荐试读
换一换
时长 04:02
时长 01:33:37
课程目录
已完结/共 41 讲
时长 00:58
时长 03:10
时长 05:29
时长 04:02
时长 01:24:35
时长 01:33:37
时长 01:16:16
时长 01:26:27
时长 30:28
时长 36:09
时长 48:57
时长 47:59
时长 54:43
时长 46:00
时长 56:31
时长 56:13
时长 53:55
时长 01:12:09
时长 51:36
时长 55:01
时长 01:35:07
时长 04:45
时长 04:08
时长 47:52
时长 45:42
时长 37:58
时长 01:13:26
时长 15:16
时长 17:22
时长 25:55
时长 14:40
时长 28:01
时长 04:15
时长 03:41
时长 03:52
算法(第 4 版)
15
15
1.0x
00:00/00:00
登录|注册

6.0.3 后缀数组

字符串处理的高效算法在科学计算和商业应用中都有着重要的地位。从搜索互联网文本信息到科学家为了揭开生命的秘密而努力研究的庞大基因数据库,21 世纪中基于字符串的计算机应用在大规模增长。和以前一样,许多经典的算法都十分有效,但人们也发明了一些很好的新算法。下面,我们将介绍能够支持这些算法的一种数据结构和一份 API。首先,我们来看一个典型的(而且是经典的)字符串处理问题。

6.0.3.1 最长重复子字符串

在给定的字符串中,至少出现了两次的最长子字符串是什么?例如,在字符串 "to be or not to be" 中,最长重复子字符串就是 "to be"。你觉得应该怎样解决这个问题呢?你能在长度为数百万个字符的字符串中找出它的最长重复子字符串吗?这个问题的说明很简单,应用也很多,包括数据压缩、密码学和计算机辅助音乐分析等。例如,开发大型软件系统中的一种常见技术叫做代码重构。程序员经常会通过复制粘贴代码从原有的程序生成新的程序。对于开发了很长时间的一大段程序,将不断重复出现的代码转化为函数调用能够使程序更加容易理解和维护。我们可以通过在程序中寻找最长重复子字符串做到这一点。这个问题的另一个应用是计算生物学。在给定的基因中存在大量相同的片段吗?同样,这个问题背后的本质也是找出字符串中的最长重复子字符串。科学家一般更关心细节(事实上,重复子字符串的意义正是科学家所希望理解的),但这个问题显然比寻找简单的最长重复子字符串更难以回答。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

本文深入介绍了后缀数组这一重要的字符串处理算法及其相关应用和性能。文章首先提出了经典的字符串处理问题:最长重复子字符串,并指出了暴力解法的局限性。随后,文章介绍了后缀排序算法的巧妙之处,以及如何利用排序算法高效地找出字符串中的最长重复子字符串。此外,还讨论了定位字符串的问题,以及在大量文本中寻找特定子字符串的应用和相关技术。文章围绕着字符串处理问题展开,介绍了相关的算法和应用,为读者提供了对字符串处理领域的深入了解。 在文章中,给出了后缀数组的 API,包括构造函数、length() 方法、select()、index()、lcp() 和 rank() 方法的用例和实现。文章还提到了后缀排序算法的性能,指出了其对长字符串的有效性和排序时间的线性对数关系。 总的来说,通过介绍后缀数组算法及其相关应用和性能,为读者提供了深入了解字符串处理领域的机会。文章内容丰富,涵盖了算法原理、API设计和性能分析,对于对字符串处理感兴趣的读者具有很高的参考价值。文章中还提到了一些改进的实现方法,使得后缀数组算法能够高效解决许多字符串处理问题,展示了算法设计和分析的重要性。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《算法(第 4 版)》
立即购买
登录 后留言

精选留言

由作者筛选后的优质留言将会公开显示,欢迎踊跃留言。
收起评论
显示
设置
留言
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部