后缀数组与ACM竞赛：理论与应用详解

"这篇IOI2004国家集训队论文由许智磊撰写，主要探讨了后缀数组在计算机科学中的核心概念和应用。后缀数组是字符串处理中的一个重要工具，它在ACM等领域具有重要意义，特别是在信息学竞赛中，因其易于编程实现、时间复杂度相对较低和空间效率较高，相比后缀树更实用。 论文首先介绍了后缀数组的基础概念，包括字符集、字符串和子串的定义，以及后缀的特定含义。后缀数组的核心在于构造，文中提到了一种O(nlogn)复杂度的倍增算法来构建后缀数组，这是一种高效的算法，能以线性对数时间复杂度完成任务。 接着，作者详细阐述了如何利用后缀数组计算最长公共前缀（LCP）的线性时间算法，这对于文本相似度分析、模式匹配等场景极为有用。LCP数组，即height数组，用于记录以每个后缀为起点、跨度为1的最长公共前缀长度，这对于多模式串的模式匹配提供了O(m+logn)的时间复杂度，这是一个重要的优化。 此外，论文还涉及了后缀数组在实际问题中的应用，如求解最长回文子串，给出了一种O(nlogn)复杂度的算法，这在字符串处理中是一项基本且常见的任务。通过这些实例，作者使读者对如何在实际编程中利用后缀数组有了直观的理解。 最后，作者对比了后缀数组和后缀树的优缺点，强调了后缀数组在信息学竞赛中的实用性。尽管后缀树在某些方面可能更直观，但后缀数组的高效性和空间节省使得它成为解决复杂字符串问题的首选工具。 这篇论文为ACM爱好者提供了一个深入理解后缀数组及其应用的宝贵资源，无论是理论学习还是实际竞赛，都具有很高的参考价值。"