后缀数组
定义
后缀数组主要是两个数组 $sa$ 和 $rk$。
$sa_i$ 表示字典序第 $i$ 小的后缀编号。
$rk_i$ 表示编号为 $i$（以第 $i$ 个字符开头）的后缀字典序排名。
显然有 $sa_{rk_i}=rk_{sa_i}=i$。
倍增求后缀数组
如何求后缀数组？
考虑倍增。
先将所有长度为 $1$ 的字符串（即每个字符）排序。
考虑当前将长度为 $w$ 的字符串排好序。
那么如何将长度为 $2w$ 的字符串排序？
只需要按 ${rk_w}[i]$ 为第一关键字，按 ${rk_w}[i+w]$ 为第二关键字排序即可。
可以用计数排序优化。
当不存在排名相同的字符串时结束即可。
时间复杂度 $O(n\log n)$，空间 $O(n)$。
有更优秀的做法可以 $O(n)$ 求后缀数组，见 OI Wiki。
后缀排序
只需要用后缀数组进行后缀排序，不需要 height 数组的题目。
height 数组
后缀数组有什么用？
只需要进行后缀排序的题目其实很少，大部分题目中还需要求一个 height 数组。
lcp 是最长公共前缀的缩写，以下 $lcp(i,j)$ 表示后缀 $i$ 和后缀 $j$ 的 最长公共前缀的长度。
height 数组的定义：$h_i=lcp(sa_i,sa_{i-1})$ 其中 $2\leq i\leq n$。
一个引理：$h_{rk_i}\geq h_{rk_{i-1}}-1$
证明：若 $h_{rk_{i-1}}\leq 1$，显然。
若 $h_{rk_{i-1}}>1$，那么后缀 $i-1$ 和 $sa_{rk_{i-1}-1}$ 存在一个长度为 $h_{rk_{i-1}}$ 的公共前缀。
所以后缀 $i$ 和 $sa_{rk_{i-1}-1}+1$ 存在一个长度为 $h_{rk_{i-1}}-1$ 的公共前缀。
并且因为后缀 $i-1$ 大于后缀 $sa_{rk_{i-1}-1}$，所以后缀 $i$ 大于后缀 $sa_{rk_{i-1}-1}+1$。
又因为 $lcp(sa_i,sa_j)=\min_{k=i+1}^j lcp(sa_{k-1},sa_k)$（这个接下来会证），所以 $lcp(i,sa_{rk_i-1})\geq lcp(i,sa_{rk_{i-1}-1}+1)\geq h_{rk_{i-1}}-1$。
知道这个引理之后，按 $i$ 从小到大暴力求 $h_{rk_i}$ 即可，因为每次最多减 $1$，所以均摊是 $O(n)$ 的。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+3;
char s[N];
int sa[N],u[N],v[N],t[N],h[N];
int main(){
int*rk=u,*b=v,n,m=131,i,j,k=0,x,y;
scanf("%s",s+1),n=strlen(s+1);
//m=131,k=0,memset(t,0,m*4+4),u[n+1]=v[n+1]=0;
//多测时加上
for(i=1;i<=n;++i)++t[s[i]];
for(i=1;i<=m;++i)t[i]+=t[i-1];
for(i=n;i;--i)sa[t[rk[i]=s[i]]--]=i;//对长度为1的字符串排序
for(i=1;k<n;m=k,i*=2){//不同的串数量等于n时停止
for(memset(t,0,m*4+4),j=n-i+1,k=0;j<=n;++j)b[++k]=j;//这里b[i]表示第二关键字为i的编号
for(j=1;j<=n;++j)if(++t[rk[j]],sa[j]>i)b[++k]=sa[j]-i;
for(j=1;j<=m;++j)t[j]+=t[j-1];
for(j=n;j;--j)sa[t[rk[b[j]]]--]=b[j];//计数排序，rk[i]为编号i的第一关键字
for(swap(rk,b),j=1,k=y=0;j<=n;++j,y=x)x=sa[j],rk[x]=b[x]==b[y]&&b[x+i]==b[y+i]?k:++k;
//这里b数组表示第一关键字，rk数组表示下一次排序的第一关键字
//b[x+i]不会越界，因为如果b[x]=b[y]，就意味着x+i-1和y+i-1都<=n
//注意有可能访问到b[n+1]，所以对于多测的题目要将u[n+1]和v[n+1]置为0
}
for(i=1,k=0;i<=n;printf("%d ",sa[i]),h[rk[i++]]=k)if(rk[i]>1)//特判h[1]
for(k=max(0,k-1),j=sa[rk[i]-1];s[i+k]==s[j+k];++k);//求h，注意可能访问到s[n+1]，但通常s[n+1]值为0不会有影响
for(i=2,puts("");i<=n;++i)printf("%d ",h[i]);
return 0;
}
配合 ST 表
height 数组的主要用途是求任意两个后缀的 lcp。
首先有性质 $lcp(sa_i,sa_j)=\min_{k=i+1}^j lcp(sa_{k-1},sa_k)$。
证明就是考虑 lcp 的长度 相当于 trie 树上的 lca 的深度。
记 $p_i$ 为 trie 树上 dfs 序为 $i$ 的点编号。
则 $lca(p_i,p_j)=lca_{k=p_i}^{p_j}k$。
证明：
首先 dfs 序在 $p_i$ 和 $p_j$ 之间的点都在 $lca(p_i,p_j)$ 的 子树内，所以这些点的一个公共祖先是 $lca(p_i,p_j)$。
又因为 $lca(p_i,p_j)$ 是 $p_i,p_j$ 的最近公共祖先，不存在深度更深的公共祖先，所以这些点的最近公共祖先是 $lca(p_i,p_j)$。
所以 $\min_{k=i+1}^j d_{lca(p_k,p_{k+1})}\geq d_{lca(p_i,p_j)}$。
又因为这些点不全在 $lca(p_i,p_j)$ 的同一个子树内，存在一个 $l$ 使得 $p_l,p_{l+1}$ 在不同子树，即 $lca(p_l,p_{l+1})=lca(p_i,p_j)$。
所以 $\min_{k=i+1}^j d_{lca(p_k,p_{k+1})}= d_{lca(p_i,p_j)}$
所以结论得证。
所以只需要用 ST 表求 height 数组区间 $\min$ 即可求出 lcp，注意特判 $i=j$。
习题：
本质不同子串个数
按字典序枚举后缀，相邻两个后缀重复的部分就是 height。
而根据之前的性质 $lcp(sa_i,sa_j)=\min_{k=i+1}^j lcp(sa_{k-1},sa_k)$，不相邻后缀不会有新的重复部分。
所以答案即为 $\dfrac{n(n-1)}{2}-\sum_{i=2}^n h_i$。
配合并查集
一种常见的套路是，求出 height 数组后，从大到小排序。
用并查集，从前到后，每次合并当前 height 对应的两个位置的信息。
习题：
配合单调栈
转化为求 $\sum_{i<j}lcp(i,j)$。
发现枚举的顺序不影响求出的答案，考虑按字典序枚举后缀 $j$，统计所有字典序小于 $j$ 的后缀 $i$ 和 $j$ 的 lcp。
这个值即为 $\sum_{i=1}^{j-1}\min_{k=i+1}^j h_k$。
对 $h$ 数组维护一个值单调递增的单调栈即可。
这个做法功能上大概可以被并查集做法替代，但是复杂度更优。
习题：
CF1073G Yet Another LCP Problem
设置关键点
用于解决和连续重复子串有关的问题。
容易发现，在一个重复部分长度为 $len$ 的连续重复子串上取两个相距为 $len$ 的点 $i,j$，则重复次数为 $\lfloor\dfrac{lcp(i,j)+lcs(i,j)+len-1}{len}\rfloor$。
考虑优化枚举点 $i,j$ 的过程。
首先枚举长度 $len$，然后将所有编号为 $len$ 的倍数的点作为关键点。
容易发现一个重复部分长度为 $len$ 的连续重复子串（重复次数至少两次）一定经过至少两个关键点，所以只需要将相邻的关键点作为 $i,j$ 即可。
枚举点对的复杂度为 $O(n\log n)$，用 ST 表求 lcp，总复杂度 $O(n\log n)$。
习题：