后缀数组
资料：https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf
一、后缀数组的定义
后缀数组（Suffix Array，简称 SA）是一种针对字符串的高效数据结构，它将字符串的所有后缀按字典序排序后，存储这些后缀的起始索引。
给定一个长度为n的字符串S = s₀s₁…sₙ₋₁，其第i个后缀为S[i:] = sᵢsᵢ₊₁…sₙ₋₁。后缀数组sa是一个长度为n的数组，满足sa[k] = i表示第k小的后缀是S[i:]，且字典序满足S[sa[0]:] < S[sa[1]:] < … < S[sa[n-1]:]。
辅助数组
为了高效处理后缀相关问题，通常会搭配两个辅助数组：
- 排名数组
rk：rk[i] = k表示后缀S[i:]在排序后的后缀数组中排名为k，与sa互为逆数组，即sa[rk[i]] = i且rk[sa[k]] = k。 - 高度数组
height：height[k]表示排名为k的后缀与排名为k-1的后缀的**最长公共前缀（LCP）**长度，即height[k] = LCP(S[sa[k]:], S[sa[k-1]:])，规定height[0] = 0。
二、后缀数组的核心特性
- 字典序有序性：后缀数组中的后缀按字典序升序排列，这是解决字符串匹配、重复子串等问题的基础。
- 排名与后缀的双向映射：通过
sa和rk可以快速查询后缀的排名，或排名对应的后缀起始索引。 - 最长公共前缀的传递性：利用
height数组可快速计算任意两个后缀的最长公共前缀长度：LCP(i,j) = min{height[rk[i]+1 ... rk[j]]}（假设rk[i] < rk[j]）。
三、后缀数组的构建算法
构建后缀数组的核心是对所有后缀进行高效排序，直接排序的时间复杂度为O(n² log n)（比较两个后缀的时间为O(n)），对于长字符串效率极低。因此需要更优的算法，常用的有：
1. 倍增算法（主流算法）
核心思想：通过倍增长度的方式，逐步确定每个后缀的排名，避免直接比较长后缀。
- 步骤：
- 初始化：先对每个字符（长度为 1 的子串）排序，得到初始的
sa和rk。 - 倍增排序：对于长度
len = 2,4,8,…，将每个后缀的前len个字符拆分为前len/2字符和后len/2字符，以(rk[i], rk[i+len/2])为关键字进行排序，更新sa和rk。 - 终止条件：当
len ≥ n时，所有后缀的排名已确定。
- 初始化：先对每个字符（长度为 1 的子串）排序，得到初始的
- 时间复杂度：
O(n log n)，实现简单且效率较高，是工程中常用的方法。
2. DC3 算法
核心思想：基于基数排序的分治算法，将后缀分为三类进行排序，进一步优化时间复杂度。
- 时间复杂度：
O(n)，但实现复杂，适合对时间要求极高的场景。
四、后缀数组的实现示例（倍增算法）
defbuild_sa(s):n=len(s)sa=list(range(n))rk=[ord(c)forcins]# 初始排名为字符的ASCII码tmp=[0]*n# 临时数组，用于排序k=1# 倍增长度whilek<n:# 排序关键字：(rk[i], rk[i+k])，i+k超出范围则为-1defcmp(i):return(rk[i],rk[i+k]ifi+k<nelse-1)# 对sa数组按新关键字排序sa.sort(key=cmp)# 更新tmp数组为新的排名tmp[sa[0]]=0p=0# 排名计数器foriinrange(1,n):# 若当前后缀与前一个后缀的关键字不同，排名+1ifcmp(sa[i])!=cmp(sa[i-1]):p+=1tmp[sa[i]]=p# 更新rk数组rk[:]=tmp[:]k*=2# 倍增长度returnsa,rkdefbuild_height(s,sa,rk):n=len(s)height=[0]*n k=0# 公共前缀长度foriinrange(n):ifrk[i]==0:continueifk>0:k-=1j=sa[rk[i]-1]# 前一个排名的后缀起始索引# 扩展公共前缀长度whilei+k<nandj+k<nands[i+k]==s[j+k]:k+=1height[rk[i]]=kreturnheight使用示例
s="abracadabra"n=len(s)sa,rk=build_sa(s)height=build_height(s,sa,rk)print("字符串:",s)print("后缀数组 sa:",sa)print("排名数组 rk:",rk)print("高度数组 height:",height)# 输出解释：# sa[0] = 10 表示排名0的后缀是 s[10:] = "a"# rk[10] = 0 表示后缀 s[10:] 排名为0# height[1] 表示排名1的后缀与排名0的后缀的最长公共前缀长度五、后缀数组的时间复杂度
- 构建（倍增算法）：
O(n log n)，其中排序的时间为O(n log n)，倍增的次数为log n。 - 高度数组构建：
O(n)，利用公共前缀的传递性，避免重复比较。 - 查询任意两后缀的 LCP：若搭配**区间最小值查询（RMQ）**预处理
height数组，查询时间为O(1)，预处理时间为O(n log n)。
六、后缀数组的典型应用
后缀数组是处理字符串问题的“万能工具”，常用于以下场景：
- 字符串匹配：在主串
S中匹配模式串P，可将P与S的后缀数组中的后缀进行二分查找，时间复杂度O(|P| log |S|)。 - 最长重复子串：字符串中出现至少两次的最长子串，其长度等于
height数组的最大值。 - 最长公共子串：给定两个字符串
S和T，拼接为S + '#' + T后构建后缀数组，找到分别来自S和T的后缀的最大height值。 - 不同子串计数：字符串中不同子串的总数为
n(n+1)/2 - sum(height[1...n-1])（总子串数减去重复子串数）。 - 后缀排序与字典序相关问题：如求字符串的最小表示、按后缀字典序输出子串等。
七、后缀数组与其他字符串结构的对比
| 数据结构 | 核心优势 | 适用场景 | 时间复杂度（构建） |
|---|---|---|---|
| 后缀数组 | 处理 LCP 问题高效，功能全面 | 重复子串、公共子串、匹配 | O(n log n) |
| 字典树（Trie） | 前缀匹配高效 | 前缀查询、词频统计 | O(n) |
| 后缀自动机（SAM） | 空间效率极高，支持动态添加 | 海量字符串的子串问题 | O(n) |
后缀数组的优势在于直观易懂且功能全面，缺点是空间复杂度较高（需存储sa、rk、height三个数组），而后缀自动机在空间和时间上更优，但理解和实现难度更大。
