后缀数组构造方法与空间优化

"后缀数组——关于空间-后缀数组--许智磊" 后缀数组是字符串处理中的一个重要数据结构，由芜湖一中许智磊所讲解。它是一种强大的工具，可作为后缀树的简洁替代品，广泛应用于现代字符串处理研究。后缀数组的核心在于对字符串的所有后缀进行字典顺序排序，从而便于高效地执行各种字符串操作。 首先，我们需要明确一些基本概念。在字符集中，字符串S的长度记为len(S)，字符串的下标从1开始，S[i]表示字符串S的第i个字符。子串是从字符串中某位置i到j的一段连续字符，表示为S[i..j]。后缀则是从位置i开始直到字符串末尾的部分，即S[i..len(S)]。 在构建后缀数组时，我们假设有一个字符集Σ，并处理一个以“$”结尾的字符串S，其中“$”是最小的字符，其余字符属于Σ。这样处理使得所有后缀的比较都能正确进行，即使它们的长度不同。排序后，我们将后缀的起始位置存储在数组SA中，这个数组就是后缀数组。同时，还有一个Rank数组，它保存了每个后缀在排序中的位置，即Rank[i]代表Suffix(i)的排名。 构建后缀数组的传统方法是直接排序，但时间复杂度高达O(n^2)，效率低下。为了提高效率，我们可以采用倍增算法（Doubling Algorithm）。该算法利用后缀之间的联系，通过k-前缀比较来逐步缩小比较范围。在k-前缀比较中，如果uk < vk，则u < kv；若uk = vk，则u = kv；若uk ≤ vk，则u ≤ kv。通过这种方式，我们可以比较两个后缀的2k-前缀，进而转化为k-前缀的比较。 具体构建过程如下：将所有后缀按k-前缀意义排序，然后将排序后的结果作为新的起始状态，再进行2k-前缀的比较和排序。重复此过程，每次翻倍k的值，直至k大于字符串长度，从而完成所有后缀的排序。在这个过程中，通过巧妙的数据结构设计，可以减少辅助计算的空间需求，比如使用Rankk和Rank2k，这两个数组可以在同一时刻只需保存一个，甚至通过技巧性操作将辅助空间降低到n个整数。 总结来说，后缀数组是一种高效处理字符串后缀的工具，通过倍增算法实现快速排序，同时利用空间优化技术减小了存储需求。理解和掌握后缀数组及其构造方法对于解决涉及字符串操作的问题具有重要意义。