线性后缀数组构建算法的描述与测试

"这篇资源是一篇关于生物信息学的学术论文，主要探讨并测试了两种新的线性后缀数组构造算法。" 在这篇2009年4月发表的论文中，作者Aurélien Bellet详细介绍了由Nong、Zhang和Chan在2008年末提出的两种新的线性后缀数组构造算法，并通过实验对比证明了它们在性能上优于已有的线性SACA算法，如KA算法和KS算法。论文首先提供了对这两种新算法直观的描述，使读者能清晰理解其主要思想。 后缀数组是字符串处理中的一个重要数据结构，它对给定字符串的所有后缀进行排序，为许多字符串算法提供高效的基础。在报告的第一部分，作者给出了基本的定义，确保读者能理解报告的内容。一个线性字符串是由有限字母集Σ中的字符组成的有限序列。论文假设这个字母集的大小是有限的。 接着，作者定义了后缀数组的概念，并简要提及其在算法应用中的重要性。后缀数组在字符串搜索、模式匹配、最长公共子串查找等生物信息学问题中扮演着关键角色，因为它允许在O(1)时间内访问和比较字符串的后缀。 1.1 基本定义 除了线性字符串的定义外，可能还包括字符集的定义，以及字符串操作的基本术语，如长度、子串、后缀等。这些定义是理解后缀数组算法的前提。 接下来的部分，作者可能详细描述了新算法的工作原理，包括它们如何在线性时间内构建后缀数组，以及与KA和KS算法相比，它们在时间和空间复杂度上的优势。此外，作者还可能引入了一个名为MP的算法，该算法在实践中比KA和KS更高效，但其最坏情况下的时间复杂度不是线性的。为了全面评估，作者将新算法与MP算法进行了比较测试。 测试部分可能涉及了各种输入规模和不同性质的字符串，以验证新算法的稳定性和效率。测试结果可能包括运行时间、内存使用以及其他性能指标的比较，从而证明新算法的有效性。 最后，论文可能会讨论新算法的局限性，可能的优化方向，以及对未来研究的影响。这不仅加深了对后缀数组构造算法的理解，也为生物信息学领域的进一步发展提供了新的思路和工具。