1 基本概念
后缀数组是一类用于处理字符串的基础数据结构。它的核心思想，是把一个字符串的所有后缀按字典序排列，并记录这些后缀在原字符串中的起始位置。由于这种表示方式紧凑、查询效率较高，它常被用于子串检索、重复模式识别、公共前缀分析等任务。
1.1 后缀与字典序
字符串的一个后缀，指从某个位置开始一直到末尾形成的子串。例如，字符串 banana 的后缀包括 banana、anana、nana、ana、na、a。将这些后缀按字典序比较时，通常从左到右逐字符判断，直到出现不同字符为止；若一个后缀是另一个后缀的前缀，则较短者在字典序中更靠前。
1.2 后缀数组的定义
后缀数组通常记作 SA。对于长度为 n 的字符串，它是一个长度同样为 n 的整数数组，其中 SA[i] 表示按字典序排在第 i 位的后缀在原串中的起始下标。换言之，SA 不是直接存储后缀文本，而是存储后缀位置的排列结果。
1.3 后缀数组的直观理解
从直观上看，后缀数组可以理解为“把所有后缀排队”。排好序以后，原来分散在字符串各处的相似片段会在数组中彼此靠近。这样一来，许多与字符串相似性有关的问题，就能转化为数组上的相邻比较、区间查询或二分检索。
1.4 相关辅助结构
后缀数组通常不会单独使用，而是与若干辅助数组配合，以便更高效地完成查询与统计。
1.4.1 排名数组
排名数组通常记作 rank，其含义与 SA 互为逆映射。rank[i] 表示原字符串中从位置 i 开始的后缀，在字典序排序后的名次。借助它，可以快速判断两个后缀的相对顺序，也便于在构造过程中更新状态。
1.4.2 高度数组
高度数组通常记作 height 或 LCP 数组。height[i] 表示 SA[i] 与 SA[i-1] 所对应后缀的最长公共前缀长度。它记录了相邻后缀之间的相似程度，是许多统计问题的关键基础。
1.4.3 最长公共前缀
最长公共前缀，通常简称 LCP，指两个字符串从开头起连续相同的最长部分。对于后缀数组而言，LCP 不仅用于描述相邻后缀的重合长度，也常被扩展到任意两个后缀之间的比较，从而支持更复杂的字符串查询。
2 构建方法
后缀数组的构建方式有多种，常见思路包括直接排序、倍增、分治以及线性时间算法。不同方法在实现难度、常数开销和适用场景上各有差异。
2.1 暴力排序法
最直接的方法是枚举全部后缀，然后使用通用排序算法按字典序排序。该方法思路简单，便于理解，但比较两个后缀时可能需要逐字符扫描，整体效率通常较低，更适合作为教学示例或小规模数据的原型实现。
2.2 倍增算法
倍增算法是构建后缀数组时最常见的方法之一。它通过不断比较长度为 1、2、4、8 等指数级增长的前缀信息，逐轮更新后缀排名，直到所有后缀的次序完全确定。
2.2.1 初始排名
算法首先根据单个字符为每个位置赋予初始排名。若字符集较小，常可直接利用字符编码建立初始序；若字符种类较多，则可先进行离散化处理，以便后续使用计数排序等线性辅助手段。
2.2.2 按长度倍增排序
在每一轮中，后缀的排序依据由“前 k 个字符”扩展为“前 2k 个字符”。做法通常是把每个后缀看成一个二元组 (rank[i], rank[i+k])，再按该键值进行排序。由于前一轮的排名已知，这种比较可以在较少信息下快速完成。
2.2.3 排名更新与收敛判断
排序完成后，需要为新的顺序重新赋排名。若相邻后缀的二元组完全相同，则赋予相同排名；否则排名递增。随着 k 不断翻倍，若所有后缀的排名都已互不相同，或者 k 已覆盖整个字符串长度，构造过程即可终止。
2.3 DC3/Skew 算法
DC3，也称 Skew 算法，是一种利用分治思想在线性时间内构造后缀数组的经典方法。它通过对部分位置先排序，再递归处理未完全确定的部分，从而避免了反复进行全量比较。
2.3.1 分治思想
该算法将后缀按下标模 3 的类别进行划分，优先处理其中一部分位置的后缀，并利用这些结果作为“骨架信息”来压缩问题规模。这样，原本复杂的全体后缀排序，就被拆解为若干规模更小的子问题。
2.3.2 核心递归流程
流程大致包括采样、对子串进行命名、递归求解采样部分的顺序、再将剩余后缀与已知顺序合并。整个过程依赖稳定的合并机制与一致的比较规则，以保证最终结果正确。
2.3.3 复杂度分析
DC3 的理论时间复杂度可达线性级别，但实现较为精细，对边界处理和索引映射要求较高。与倍增算法相比，它在大规模数据上更具理论优势，但工程实现难度也明显更大。
2.4 SA-IS 算法
SA-IS 是另一种线性时间构建方法，常被认为是后缀数组构造中的高效代表。它通过区分不同类型字符，并对关键子串进行诱导排序，逐步恢复完整的后缀顺序。
2.4.1 S 型与 L 型字符划分
SA-IS 会先把每个位置划分为 S 型或 L 型。一般而言，若当前位置后缀在字典序上小于右侧后缀，则记为 S 型；否则记为 L 型。这样的分类为后续识别关键位置提供了基础。
2.4.2 LMS 子串
LMS 指“左端为 S 型且前一个位置为 L 型”的特殊位置。以这些位置为边界切出的子串，具有较强的代表性。算法通常先对 LMS 子串排序和命名，再借助这些名称压缩原问题。
2.4.3 诱导排序
诱导排序是 SA-IS 的关键步骤之一。它利用已知的部分后缀顺序，逐步推导相邻位置的排序结果，从而恢复更大范围内的后缀排列。该过程避免了对所有后缀进行直接比较，因而能够达到较高效率。
3 相关数组与性质
后缀数组的价值不仅在于“排序”，更在于它揭示了字符串内部的结构关系。排名数组、高度数组以及相邻后缀之间的性质，共同构成了后缀数组应用的理论基础。
3.1 排名数组的作用
排名数组能够把“原串位置”直接映射到“后缀名次”。当需要判断某个后缀是否出现在特定区间、或者比较两个后缀在全局中的先后关系时，rank 提供了比反复查表更直接的方式。
3.2 高度数组的含义
高度数组记录了后缀排序后相邻元素之间的相似程度。由于相邻后缀往往共享较长前缀，因此 height 数组可以帮助快速发现重复片段、公共结构以及局部模式，是后缀数组体系中极为重要的一环。
3.3 相邻后缀的公共前缀性质
在后缀数组中，两个后缀若在排序中位置接近，往往意味着它们的公共前缀较长。更进一步地，对于任意两个后缀，它们的最长公共前缀可以通过区间内 height 的最小值推导出来。这一性质使得很多原本需要逐字符比较的问题，转化为数组区间查询问题。
3.4 单调性与区间性质
后缀数组及其配套数组常呈现出较强的单调特征。例如，相邻后缀的公共前缀在局部上具有连续性，某些统计量则可借助区间最值、区间覆盖来完成。正因如此，后缀数组与 RMQ、单调栈等工具具有天然的兼容性。
4 核心应用
后缀数组之所以重要，在于它能够支撑大量字符串问题。许多看似不同的任务，最终都可归结为排序、比较、区间处理或统计。
4.1 子串查找
子串查找是后缀数组最经典的用途之一。由于所有后缀已经按字典序排列，某个模式串是否出现在原串中，可以通过比较模式串与后缀的前缀关系来判断。
4.1.1 二分定位
对后缀数组进行二分搜索，可以找到所有以给定模式串为前缀的后缀所对应的连续区间。只要区间不为空，就说明模式串在原串中至少出现一次；若进一步统计区间长度，还能得到出现次数。
4.1.2 多模式匹配
当需要在同一文本中查询多个模式串时，后缀数组可以复用同一套排序结果。多个查询分别进行二分定位即可，避免了重复构建结构，适合静态文本上的批量检索。
4.2 重复子串问题
后缀数组对于重复结构的分析非常有效，尤其适合寻找最长重复片段、计算重复出现的规模，以及识别局部模式。
4.2.1 最长重复子串
最长重复子串通常可以通过 height 数组求得。因为任意两个相邻后缀的最长公共前缀都被记录在其中，所以整个字符串中最长的重复部分，往往对应 height 的最大值。
4.2.2 重复次数统计
若某个子串在多个位置重复出现，可以在后缀数组中表现为一段相邻后缀共享较长前缀。借助这些连续区间，可以统计某一模式出现的次数，或者分析某一重复片段的覆盖范围。
4.3 最长公共子串
最长公共子串是后缀数组的另一类典型应用。它用于比较两个或多个字符串中共有的连续片段长度。
4.3.1 双串拼接处理
对两个字符串进行拼接，并插入分隔符后，可以在同一后缀数组上统一处理。只要确保分隔符不会与原字符混淆，就能通过观察来自不同原串的后缀之间的公共前缀，求出最长公共子串。
4.3.2 多串扩展
对于多个字符串，也可以采用拼接与标记归属的方式进行扩展。统计时需要判断某个后缀区间是否同时覆盖了多个来源字符串，从而找出它们的共同连续片段。
4.4 本质不同子串计数
后缀数组还可以用于统计一个字符串中不同子串的总数。思路通常是：以每个后缀为起点，它能贡献的子串数量等于其长度减去与前一个后缀的公共前缀长度。将这些贡献累加，即可得到本质不同子串的总数。
4.5 字典序相关查询
由于后缀数组本身就是按字典序组织的信息结构，因此它非常适合处理与“第几小”“最早出现”“字典序最小”等问题相关的查询。
4.5.1 第 k 小子串
第 k 小子串问题通常需要结合后缀数组与前缀贡献统计。每个后缀能提供一批按字典序排列的子串，而前缀长度与 height 的差值决定了新增部分。通过累积这些数量，可以定位目标子串。
4.5.2 字符串最小表示相关问题
在某些字符串变形任务中，需要判断循环同构串的字典序最小表示。虽然这类问题常有专门算法，但后缀数组也能作为辅助工具，用于比较不同起点形成的循环串，从而找到最小的字典序代表。
5 进阶配套技术
在实际应用中，后缀数组很少孤立存在。围绕它形成的一整套配套技术，使得 LCP 查询、区间统计和复杂模式识别都能高效完成。
5.1 RMQ 与 LCP 查询
RMQ 即区间最值查询。由于任意两个后缀的 LCP 可转化为 height 数组上的区间最小值问题，因此 RMQ 是后缀数组查询体系中的重要工具。
5.1.1 线段树实现
线段树可以用于维护 height 数组上的区间最小值，支持动态或半动态场景下的查询。它的优点是实现通用，适应性较强；不足之处在于常数略大，且预处理与查询都带有额外开销。
5.1.2 稀疏表实现
稀疏表适合静态区间最值查询。由于 height 数组通常在构建后不再修改，稀疏表能以较低查询成本快速给出区间最小值，因而在竞赛和工程中都很常见。
5.2 单调栈与高度数组应用
高度数组在某些统计问题中可以配合单调栈使用。例如，当需要分析连续相似后缀形成的区间时，单调栈可帮助寻找左、右边界，从而计算满足条件的子区间数量。这类方法常用于重复结构计数和区间贡献分析。
5.3 与后缀自动机的对比
后缀自动机同样擅长处理子串问题，且在很多场景下构建更直接、状态更紧凑。相比之下，后缀数组更偏向排序与区间比较，后缀自动机则更适合在线扩展和子串集合管理。两者都可作为字符串算法中的核心工具，适用范围略有侧重。
5.4 与后缀树的对比
后缀树在结构表达上更直观，能够显式表示大量公共前缀关系；但它通常较为庞大，工程实现也更复杂。后缀数组则更节省空间，便于结合普通数组结构与经典算法实现，因此在许多实际场合中更易落地。
6 复杂度分析
后缀数组的效率与所采用的构建算法关系很大。不同方案在时间和空间上的表现差别明显，因此实际选型时需要结合数据规模与实现成本综合考虑。
6.1 时间复杂度
暴力排序通常效率较低，依赖比较器实现，最坏情况下比较代价较高。倍增算法一般可达到 O(n log n) 级别。DC3 和 SA-IS 则具有线性时间构建的理论优势，但常数和实现复杂度更高。
6.2 空间复杂度
后缀数组本身只需存储若干整数数组，空间占用通常比后缀树小得多。倍增算法往往需要多组辅助数组；线性算法也会使用额外缓冲区和中间标记，但总体上仍较为紧凑。
6.3 不同构建算法的性能比较
从工程实践看，倍增算法通常是最常见的平衡方案，原因在于它实现相对清晰、调试友好，且在大多数场景下性能足够。DC3 与 SA-IS 更适合对理论复杂度要求较高的场合；暴力排序则主要用于教学或极小规模数据。
7 实现细节
后缀数组虽是经典结构，但真正实现时仍有不少细节需要处理。字符编码、边界、排序稳定性等因素，都会影响最终结果。
7.1 字符编码与哨兵处理
很多实现会在字符串末尾添加一个最小哨兵字符，用于统一处理边界并保证所有后缀可比较。字符集较大时，往往还需要先进行编码压缩，以减少排序时的键值范围。
7.2 边界条件处理
在处理长度较短、重复字符较多或包含空串前缀的情况时，边界最容易出错。特别是在倍增算法里，访问 rank[i+k] 时要注意越界位置的默认值设定，否则会导致排序结果偏差。
7.3 稳定排序与计数排序
倍增构造中常会用到计数排序或基于桶的排序方式，以保证对二元组排序的效率与稳定性。稳定性对于多轮排名更新很重要，因为它直接关系到相等键值在下一轮中的相对位置是否被正确保留。
7.4 常见调试问题
常见问题包括下标从 0 还是 1 开始不一致、哨兵字符大小设定错误、height 计算时未正确复用前缀信息，以及多组数据时数组未清空等。此类问题往往不会立刻报错，却会让结果出现细微偏差，因此调试时需要格外谨慎。
8 典型例题与模式
后缀数组在题目中的出现形式往往比较固定，熟悉常见模板有助于快速识别并选用合适方法。
8.1 经典字符串题型
经典题型包括最长重复子串、最长公共子串、本质不同子串计数、模式串出现次数查询、字典序第 k 小子串等。这些问题大多可以通过后缀数组加 height 或 RMQ 的组合来处理。
8.2 算法竞赛中的常见模板
竞赛中常见的模板做法通常包含：构建 SA、求 rank 与 height、预处理 RMQ、支持 LCP 查询、再在此基础上完成统计或二分判断。掌握这一模板后，许多题目可以直接套用基础框架再做少量扩展。
8.3 工程实现中的注意事项
工程环境中更关注稳定性和可维护性。实际使用时，通常需要考虑字符集兼容、输入规模、内存限制和接口封装等因素。若字符串处理任务较频繁，合理封装后缀数组及其配套查询接口，会比单次编写零散代码更可靠。