后缀数组：构造与应用详解——IOI2009国家集训队论文

"后缀数组——处理字符串的有力工具"是一篇针对信息学奥林匹克竞赛的国家集训队论文，由罗穗骞撰写，得到了张学东老师的指导。该文章主要分为两大部分：后缀数组的构造方法及其应用。 首先，文章详细介绍了后缀数组的基本概念。后缀数组是字符串处理中的核心数据结构，它将字符串的所有后缀按照字典序排序，使得查找最长公共前缀、重复子串、子串数量、回文子串等问题变得高效。作者着重讨论了两种构造后缀数组的方法：一种是倍增算法，通过递归构建后缀数组，其特点是直观易懂但计算复杂度较高；另一种是DC3算法，这是一种基于前缀函数和双指针技巧的优化算法，虽然初始复杂度稍高，但在实际应用中效率显著提升。 在倍增算法部分，作者不仅给出了算法原理，还提供了简洁且高效的代码实现，并对比了两种算法的时间复杂度和空间复杂度，帮助读者理解它们各自的优缺点。倍增算法适用于小规模字符串，而DC3算法则在处理大规模数据时更显优势。 第二部分，文章深入探讨了后缀数组在实际问题中的应用。例如，作者通过实例演示了如何使用后缀数组求解最长公共前缀问题，以及解决单个字符串相关的重复子串（包括可重叠和不可重叠情况）、子串个数、回文子串（如最长回文子串）和连续重复子串等问题。每个例子都配以具体的题目引用，如"pku1743"和"ural1297"，让读者能够将理论知识与实际竞赛题目相结合。 这篇论文不仅提供了一种强大的字符串处理工具——后缀数组的详细介绍，还展示了其在信息学竞赛中解决典型问题的实际应用技巧。这对于参加信息学竞赛的学生和对字符串处理感兴趣的读者来说，是一份宝贵的参考资料。