字符串

本文字符串下标从 $1$ 开始，无歧义时默认 $n$ 为当前所述字符串长度。

后缀数组（SA）

定义 $suf_i\gets s[i,n]$，$rk_i$ 为 $suf_i$ 在所有后缀中的字典序排名，$sa_i$ 为字典序第 $i$ 小的后缀。$rk,sa$ 互逆。

例如 $s=\texttt{aabab}$ 时，$\texttt{aabab}<\texttt{ab}<\texttt{abab}<\texttt{b}<\texttt{bab}$，所以 $rk=[1,3,5,2,4],sa=[1,4,2,5,3]$。

后缀排序指求上述数组的过程。

$O(n\log^2n)$ 做法

考虑朴素倍增。不妨定义 $rk'_{i,j}$ 表示将 $s[*,*+2^j-1]$ 按字典序排序后 $s[i,i+2^j-1]$ 的排名，$sa'_{i,j}$ 同理。

倍增分为 $\log n$ 轮，第 $j$ 轮得到 $rk'_{i,j},sa'_{i,j}$。

具体地，在第 $j$ 轮中，按 $\left(rk'_{*,j-1},rk'_{*+2^{j-1}-1,j-1}\right)$ 排序，得到 $sa'_{i,j}$ 并推出 $rk'_{i,j}$，注意需要去重。

最终 $rk_i\gets rk'_{i,\log n},sa_i\gets sa'_{i,\log n}$，即倍增覆盖长度大于 $n$，使 $suf_i$ 等价于 $s[i,i+2^j-1]$ 后结束。

$O(n\log n)$ 做法

考虑到两个关键字的值域都为 $O(n)$，可以使用基数排序，复杂度即可优化到 $O(n\log n)$。

#include <bits/stdc++.h>

using std::cin;
typedef long long ll;
constexpr int N=2e6+114;
int n;
std::string s;
int sa[N],rk[N],id[N],ork[N],buc[N];

inline void build()
{
    int m=1<<7,k=0;
    for(int i=1;i<=n;i++)buc[rk[i]=s[i]]++;
    for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
    for(int i=n;i;i--)sa[buc[rk[i]]--]=i;
    for(int j=1;;m=k,k=0,j<<=1)
    {
        for(int i=n-j+1;i<=n;i++)id[++k]=i;
        for(int i=1;i<=n;i++)if(sa[i]>j)id[++k]=sa[i]-j;
        std::fill(buc+1,buc+m*2+1,0);
        std::copy(rk+1,rk+n*2+1,ork+1);
        k=0;
        for(int i=1;i<=n;i++)buc[rk[i]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n;i;i--)sa[buc[rk[id[i]]]--]=id[i];
        for(int i=1;i<=n;i++)rk[sa[i]]=
            (ork[sa[i-1]]==ork[sa[i]]&&ork[sa[i-1]+j]==ork[sa[i]+j])?k:++k;
        if(k==n)break;
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>s;
    n=s.size();
    s=' '+s;
    build();
    for(int i=1;i<=n;i++)printf("%d ",sa[i]);
    return 0;
}

注意 $rk'$ 严格满足排名的定义（即小于本身的不同元素的数量），可以维护 $rk'_{i,j}$ 的值域 $m$，当 $m=n$ 时直接退出。

同时对第二关键字的排序是不必要的，对于 $i\in[n-2^j+1,n]$，$rk'_{i+2^j,j-1}=0$，直接将它们放置在 $sa'_{i,j}$ 的开头，其他的按照 $rk'_{i+2^j,j-1}$ 顺序即可。

$ht$ 数组

记 $\operatorname{lcp}(i,j)$ 为 $suf_i,suf_j$ 的最长公共前缀，$ht_i\gets|\operatorname{lcp}(sa_{i-1},sa_i)|,ht_1\gets 0$。

结论 1 若 $rk_i\le rk_j\le rk_k$，则 $|\operatorname{lcp}(i,j)|,|\operatorname{lcp}(j,k)|\ge\operatorname{lcp}(i,k)$。

结合图片容易理解，$\operatorname{lcp}$ 实际上是一个取区间 $\min$，也就是说：

结论 2 若 $rk_i<rk_j$，则 $|\operatorname{lcp}(i,j)|=\min\limits_{k=rk(i)+1}^{rk(j)}ht_k$。

大区间的最小值自然不大于其子区间的最小值。

求 $ht$ 数组所需的一个重要引理：

$ht(rk_i)\ge ht(rk_{i-1})-1$

证明

记 $i-1$ 的前驱 $p\gets sa(rk_{i-1}-1)$，根据定义 $ht(rk_{i-1})=|\operatorname{lcp}(sa(rk_{i-1}-1),sa(rk_{i-1}))|=|\operatorname{lcp}(p,i-1)|$。

假设 $ht(rk_{i-1})>0$，则显然

$\begin{aligned} |\operatorname{lcp}(p+1,i)|&=|\operatorname{lcp}(p+1,i-1+1)|\\ &=|\operatorname{lcp}(sa(rk_{i-1}-1)+1,sa(rk_{i-1})+1)|\\ &=|\operatorname{lcp}(sa(rk_{i-1}-1),sa(rk_{i-1}))|-1\\ &=ht(rk_{i-1})-1 \end{aligned}$

即同时删去第一个字符，$\operatorname{lcp}$ 减 $1$。

同时因为 $ht(rk_{i-1})>0,rk_p<rk_{i-1}$，不难发现 $rk_{p+1}<rk_i$。根据结论 1，

$\begin{aligned} |\operatorname{lcp}(sa(rk_i-1),i)|&\ge|\operatorname{lcp}(p+1,i)|\\ ht(rk_i)&\ge ht(rk_{i-1})-1\\ \end{aligned}$

$\square$

以上内容可以结合下图理解。

s=aabbaba
p=sa(rk(i)-1)

ind    rk	suf		p.s.
7    1	a		p+1
1    2	aabbaba	sa(rk_i-1)
5    3	aba		i
2    4	abbaba	
6    5	ba		p
4    6	baba	i-1
3    7	bbaba	

这样，我们就有了均摊 $O(n)$ 求 $ht$ 数组的优美做法。

for(int i=1,k=0;i<=n;i++)
{
    if(k)k--;
    while(s[i+k]==s[sa[rk[i]-1]+k])k++;
    ht[rk[i]]=k;
}