构建后缀数组算法综述：空间效率与复杂性比较

后缀数组是一种高效的数据结构，最初由Manber和Myers在1990年提出，作为一种空间节省的替代方案，用于处理字符串的后缀关系问题，尤其是在文本搜索、模式匹配和字符串排序等领域。相比于传统的后缀树，后缀数组更易于存储和操作，特别适合于大规模数据处理。 该篇论文详细探讨了后缀数组构造算法的多样性和发展。自Manber-Myers算法以来，出现了大量创新的后缀数组构建方法，这些算法各有特色，旨在提高构建效率、空间利用以及查询性能。作者Simon Puglisi、W.F. Smyth和Andrew Turpin对这些算法进行了系统的梳理，提供了高层面的描述，强调了它们的共同点和差异性，但尽可能避免深入讨论实现细节的复杂性。 论文列举了多种算法，包括但不限于线性时间复杂度的KMP算法、Boyer-Moore算法的变种、SA-IS（Semi-external Incremental Suffix Array）算法，以及更近期提出的混合算法。这些算法在最坏情况下的时间复杂度各不相同，有的在时间上更高效，有的则在空间效率上更有优势。 此外，作者还对比了这些算法在理论上的性能指标，如时间复杂度的上界和下界，以及额外空间的消耗。同时，论文还分享了对多种算法实现的实验测试结果，这些实证数据有助于读者了解不同算法在实际应用中的表现和适用场景。 这篇论文不仅提供了丰富的算法分类和分析，还为研究人员和工程师们提供了一个全面的后缀数组构建算法参考框架，帮助他们根据具体需求选择最合适的算法，并理解其背后的原理和优缺点。对于从事IT领域的专业人士，理解和掌握这些算法是提升字符串处理能力的关键，对于优化文本处理任务具有重要意义。