后缀数组：字符串处理的利器

"后缀数组详解 - IOI2009国家集训队论文 - 罗穗骞" 后缀数组是一种数据结构，用于高效地处理字符串的各种问题，如查找最长公共前缀、重复子串、子串个数、回文子串等。在计算机科学和信息学奥林匹克竞赛中，后缀数组是解决字符串问题的关键工具。 **基本定义** 后缀数组是一个数组，包含了给定字符串的所有后缀，并按照某种排序规则排列。例如，对于字符串 "abcde"，其后缀数组就是 ["e", "de", "cde", "bcde", "abcde"]。排序规则通常是字典序或根据某个自定义的比较函数。 **实现算法** 1. **倍增算法**：这是一种常用的构建后缀数组的方法。它通过多次比较后缀的前几个字符来逐步确定后缀的相对顺序。每次比较的长度翻倍，直到所有后缀都能确定位置。这种方法的时间复杂度可以达到 O(n log n)。 2. **DC3算法**（DAMICHI-3）：DC3算法是一种基于字符的三分法，将字符串的字符分为三类，然后通过比较后缀中不同类别的字符来快速排序。相比于倍增算法，DC3在某些情况下可能更快，但通常实现较为复杂。 **算法比较** 倍增算法和DC3算法都是构建后缀数组的有效方法。倍增算法易于理解和实现，而DC3算法在特定条件下可能提供更好的性能。实际应用中，根据字符串的特性和问题的需求选择合适的算法。 **后缀数组的应用** 1. **最长公共前缀**：后缀数组可以用来找到字符串集合中的最长公共前缀。通过比较后缀数组中相邻后缀的共同部分，可以快速找到公共前缀。 2. **单个字符串的相关问题**： - **重复子串**：利用后缀数组可以找出字符串中的重复子串，包括可重叠和不可重叠的情况。 - **子串个数**：可以计算出不相同的子串数量，例如在给出的SPJ题目中，通过后缀数组计算所有不同子串的数量。 - **回文子串**：后缀数组结合LCP（最长公共前后缀）数组可以有效地找出最长的回文子串，如Ural1297题目所示。 - **连续重复子串**：通过后缀数组，可以找到连续重复的子串，如Pku题目所示。 后缀数组的这些应用体现了它的强大之处，特别是在处理字符串问题时，能够提供线性时间复杂度的解决方案。在信息学竞赛和实际编程中，掌握后缀数组的原理和应用对于解决字符串相关的复杂问题至关重要。