后缀数组
2026-08-07
流程
最普通的 SA 需要两个数组:sa 和 rk。
其中 sa[i] 表示所有后缀中,字典序排名为 i 的后缀的起始字符串下标。
rk[i] 表示起始下标为 i 的后缀的字典序排名。
容易发现,这两个数组的定义是相反的,也就是说:sa[rk[i]]=i,rk[sa[i]]=i。
接下来的问题变成了如何求 sa 和 rk,一个比较直白的想法是直接枚举所有后缀然后排序,可是时间复杂度 O(n2logn),考虑如何优化。
我们每次都是一个一个比较,有没有什么办法一次比较多个呢?有的有的,倍增了解一下:
- 对于第一次排序,我们以每个后缀的第一个字母(这不就是原序列)为第一关键字进行排序,得到第一次的 sa1,rk1。
- 第二次排序,我们将每个后缀的 rk1[i] 作为第一关键字,第一个字母向后 20=1 个字母为第二关键字排序,得到 sa2,rk2。
以此类推,每次都以上一次的 rki 作为第一关键字,然后将向后偏移 2i 作为第二关键字,排序后求出新的 sai+1,rki+1。
特别的,如果一个字符向后的位置没有字符,将其第二关键字视为 0(其实可以直接塞到排序完的序列里)。
这么做是 O(nlog2n) 的,还可以继续优化到 O(nlogn),即利用基数排序,这样能将排序做到 O(n),总复杂度即为 O(nlogn)。
代码实现
代码模板放在模板集合里了,这里我们分开讲实现。
首先是预处理,我们将所有 s[i] 作为第 i 个后缀的第一关键字进行排序:
for(int i = 1 ; i <= n ; i ++) c[x[i] = s[i]] ++;
for(int i = 2 ; i <= m ; i ++) c[i] += c[i-1];
for(int i = n ; i >= 1 ; i --) sa[c[x[i]] --] = i;注意,这里 c[i] 表示不大于 ASCII 码为 i 的后缀有多少个,最终后续填充 sa 保证了稳定性(关键字相同时,相对顺序不变)。
然后,我们开始倍增循环:
for(int k = 1 ; k <= n ; k <<= 1) {
int num = 0;
for(int i = n-k+1 ; i <= n ; i ++) y[++ num] = i;
for(int i = 1 ; i <= n ; i ++)
if(sa[i] > k) y[++ num] = sa[i]-k;
for(int i = 1 ; i <= m ; i ++) c[i] = 0;
for(int i = 1 ; i <= n ; i ++) c[x[i]] ++;
for(int i = 2 ; i <= m ; i ++) c[i] += c[i-1];
for(int i = n ; i >= 1 ; i --) sa[c[x[y[i]]] --] = y[i] , y[i] = 0;
swap(x , y);
x[sa[1]] = 1; num = 1;
for(int i = 2 ; i <= n ; i ++)
x[sa[i]] = (y[sa[i]] == y[sa[i-1]] &&
y[sa[i]+k] == y[sa[i-1]+k]) ? num : ++ num;
if(num == n) break;
m = num;
}我们拆成三大段来看:
第一段中,y 是第二关键字排序下标的结果,没有第二关键字的 (n−k,n] 直接放入 y 中,然后,我们保持原相对顺序,将所有能作为第二关键字的 sa[i],其对应的 sa[i]−k 放入 y 中,这样就完成了第二关键字的排序。
第二段中,清空 c 并统计第一关键字 x 的出现次数,按照 y 的逆序遍历放入 sa 中(y 的逆序保证了第二关键字大的在右边),然后清空 y。
第三段中,交换 x,y,此时 y 中存储的是长度为 k 的排名,我们要将 x 重新赋值为 2k 的排名,注意,这里 y[sa[i]] == y[sa[i-1]] && y[sa[i]+k] == y[sa[i-1]+k] 最多越界到 n+1,所以并不需要开大数组(因为 && 的短路性质)。
除了这两个数组,SA 一般都会维护一个数组 ht,定义为 ht[i]=LCP(sa[i],sa[i−1]),即排名为 i 的后缀和排名为 i−1 的后缀的最长公共前缀。
这玩意有啥用?对于两个后缀 i,j,它们的 LCP 长度即为 k=rk[i]+1minrk[j]ht[k](假设 rk[i]<rk[j])。
引理
对于任意 i∈[2,n] 且 rk[i]>1,有:
ht[rk[i]]≥ht[rk[i−1]]−1
证明
我们设 A 为 i−1 的后缀, B 为 i 的后缀。
我们假设 A 的 ht 为 L,即 L=ht[rk[i−1]]。
设 sa[rk[i−1]−1] 对应的后缀为 P,由 L=ht[rk[i−1]]=LCP(A,sa[rk[i−1]−1])=LCP(A,P)。
接下来,我们将 A,P 同时去掉第一个字母,由于 A,P 的 LCP 相等,所以 A′,B,P′ 的前 L−1 个字母相同,由于 P 仍为 A 前缀,
