后缀数组：线性算法与构造方法解析

"后缀数组是字符串处理中的一个重要概念，它是由字符串的所有后缀按照字典顺序排序后的位置数组。在本文中，作者许智磊介绍了后缀数组的定义、符号以及构建方法，特别提到了线性时间复杂度的Farach构造方法，尽管这个方法不在考察范围内。后缀数组是字符串搜索、模式匹配等问题的有效工具，它的构建方法之一是倍增算法（Doubling Algorithm），通过逐步增加比较的前缀长度来优化排序过程。 后缀数组的基本定义包括字符集、字符串长度、子串以及后缀的概念。字符集Σ包含所有可能的字符，字符串S的长度为n，并且下标从1开始。字符串S[i..j]表示从位置i到j的子串，而S[i..len(S)]则表示从位置i开始到字符串末尾的后缀。为了方便比较，字符串S的末尾添加了一个特殊字符“$”，并且“$”小于Σ中的所有字符。 构建后缀数组的典型方法是首先按照常规字符串排序的方式尝试对后缀排序，但由于忽略了后缀之间的内在联系，这种方法效率低下，时间复杂度为O(n^2)。为了提高效率，倍增算法被引入。该算法基于k-前缀比较关系，比较字符串u和v的前k个字符来确定它们的相对顺序。随着k的逐渐增加，可以逐步确定后缀的精确顺序，这样可以在O(n)的时间复杂度内完成后缀数组的构造。 在倍增算法中，比较两个后缀u和v时，首先比较它们的前k个字符，然后如果前k个字符相同，则继续比较第k+1到2k个字符，以此类推。通过这种方式，可以将2k-前缀的比较转化为k-前缀的比较，简化了比较过程。最后，根据这些比较结果，将后缀按顺序放入数组SA（后缀数组）中，并生成Rank数组记录每个后缀的排名。 后缀数组和名次数组（Rank数组）是字符串处理中的核心数据结构，它们广泛应用于各种字符串算法中，如LCP（最长公共前后缀）数组的计算、Manacher's Algorithm（用于找出字符串中的所有回文子串）、AC自动机等。通过理解并掌握后缀数组及其构造方法，开发者能够在解决涉及字符串的问题时获得显著的性能优势。