数据结构：后缀数组

后缀数组

资料：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]:]。

辅助数组

为了高效处理后缀相关问题，通常会搭配两个辅助数组：

1. 排名数组rk：rk[i] = k表示后缀S[i:]在排序后的后缀数组中排名为k，与sa互为逆数组，即sa[rk[i]] = i且rk[sa[k]] = k。
2. 高度数组height：height[k]表示排名为k的后缀与排名为k-1的后缀的**最长公共前缀（LCP）**长度，即height[k] = LCP(S[sa[k]:], S[sa[k-1]:])，规定height[0] = 0。

二、后缀数组的核心特性

1. 字典序有序性：后缀数组中的后缀按字典序升序排列，这是解决字符串匹配、重复子串等问题的基础。
2. 排名与后缀的双向映射：通过sa和rk可以快速查询后缀的排名，或排名对应的后缀起始索引。
3. 最长公共前缀的传递性：利用height数组可快速计算任意两个后缀的最长公共前缀长度：LCP(i,j) = min{height[rk[i]+1 ... rk[j]]}（假设rk[i] < rk[j]）。

三、后缀数组的构建算法

构建后缀数组的核心是对所有后缀进行高效排序，直接排序的时间复杂度为O(n² log n)（比较两个后缀的时间为O(n)），对于长字符串效率极低。因此需要更优的算法，常用的有：

1. 倍增算法（主流算法）

核心思想：通过倍增长度的方式，逐步确定每个后缀的排名，避免直接比较长后缀。

• 步骤：
  1. 初始化：先对每个字符（长度为 1 的子串）排序，得到初始的sa和rk。
  2. 倍增排序：对于长度len = 2,4,8,…，将每个后缀的前len个字符拆分为前len/2字符和后len/2字符，以(rk[i], rk[i+len/2])为关键字进行排序，更新sa和rk。
  3. 终止条件：当len ≥ n时，所有后缀的排名已确定。
• 时间复杂度：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)。

六、后缀数组的典型应用

后缀数组是处理字符串问题的“万能工具”，常用于以下场景：

1. 字符串匹配：在主串S中匹配模式串P，可将P与S的后缀数组中的后缀进行二分查找，时间复杂度O(|P| log |S|)。
2. 最长重复子串：字符串中出现至少两次的最长子串，其长度等于height数组的最大值。
3. 最长公共子串：给定两个字符串S和T，拼接为S + '#' + T后构建后缀数组，找到分别来自S和T的后缀的最大height值。
4. 不同子串计数：字符串中不同子串的总数为n(n+1)/2 - sum(height[1...n-1])（总子串数减去重复子串数）。
5. 后缀排序与字典序相关问题：如求字符串的最小表示、按后缀字典序输出子串等。

七、后缀数组与其他字符串结构的对比

后缀数组的优势在于直观易懂且功能全面，缺点是空间复杂度较高（需存储sa、rk、height三个数组），而后缀自动机在空间和时间上更优，但理解和实现难度更大。