后缀数组详解：构造与应用

【标题】"2014-许智磊-后缀数组1"这篇论文深入探讨了后缀数组在计算机科学中的关键概念、构造方法以及其在实际问题中的应用。作者许智磊，来自安徽省芜湖市第一中学，针对IOI2004国家集训队的研究背景，提供了详尽的讲解。 【摘要】文章首先介绍了后缀数组的基本概念，它是字符串处理中的一个重要工具，尤其是在信息学竞赛中因其效率和空间效率而被广泛应用。后缀数组是一种数据结构，用于存储字符串的所有后缀，并按照它们在原字符串中的字典序进行排序。构建后缀数组的关键算法是倍增法，该方法可以在O(nlogn)的时间复杂度内完成，显著优于后缀树的构建。 其次，文章重点讨论了如何利用后缀数组计算最长公共前缀（LCP），这是一个重要的辅助数组，用于查找具有特定长度的相同前缀。通过介绍线性时间计算height数组的方法，读者能更好地理解如何在实际操作中高效地使用这些数据结构。 文章还展示了后缀数组在实际问题中的应用，如多模式串的模式匹配，通过后缀数组可以实现O(m+logn)的匹配时间复杂度，以及求解最长回文子串，使用后缀数组可以达到O(nlogn)的效率。这些应用实例有助于读者直观感受后缀数组的实用性。 最后，作者对比了后缀数组与后缀树，强调了后缀数组在编程实现上的易用性和空间效率优势，尽管后缀树在某些特定场景下可能更直观，但在信息学竞赛等对时间和空间限制严格的环境中，后缀数组显得更加实用。 这篇论文为读者提供了一个全面理解后缀数组的框架，包括理论基础、核心算法和实际应用场景，是学习和研究字符串处理算法的重要参考资料。