字符串 3
后缀数组
算法简介
后缀树的一种替代品，可以用于解决各种字符串问题。
算法实现
后缀数组的核心为 $sa$ 数组，$rk$ 数组以及 $\text{height}_i$ 数组。
其中 $sa_i$ 表示排名为 $i$ 的后缀的起始位置，$rk_i$ 表示起始位置为 $i$ 的后缀的排名。
$sa$ 数组可以通过倍增法和基数排序求解，时间复杂度 $O(n\log n)$，根据 $rk_{sa_i}=i$ 可以 $O(n)$ 求解 $rk$ 数组。
$\text{height}_i$ 表示 $\text{LCA}(S[sa_i,n],S[sa_{i-1},n])$ 的长度，给出引理
$$\text{height}_{rk_i}\ge \text{height}_{rk_{i-1}}-1$$
显然 $\text{height}_{rk_i}=\text{LCA}(S[i,n],S[sa_{rk_i-1},n]),\text{height}_{rk_{i-1}}=\text{LCA}(S[i-1,n],S[sa_{rk_{i-1}-1},n])$。
假设 $S[i-1,i-1+k]=S[j,j+k]$，显然有 $S[i,i-1+k]=S[j+1,j+k]$，于是上述引理得证。
根据引理，可以 $O(n)$ 求解 $\text{height}_i$ 数组。
算法例题
例题一
题意
给定字符串 $S=s_1s_2\cdots s_n$，将其视为一个环，任意选择环的起点，可以得到 $n$ 个新字符串 $T_k=s_ks_{k+1}\cdots s_{k-1}$。
询问将所有 $T_i$ 按字典序从小到大排序后依次取每个 $T_i$ 的最后一个字母构成的字符串。
题解
考虑将 $S$ 倍长为 $SS$，求 $SS$ 每个后缀的排名，即可得到每个字符串 $T_i$ 的排名。
关于正确性，考虑字符串 $abc$，于是 $T_2$ 代表的字符串 $bca$ 变为 $bcabc$，实际上这相当于 $T_2$ 再与 $T_2$ 的前缀拼接而成，不影响排序结果。
时间复杂度 $O(n\log n)$。
例题二
题意
给定一个字符串 $S$ 和一个空串 $T$，每个可以选择 $S$ 的首字符或末字符，将其删去后加入到 $T$ 末尾。
问所有可能的 $T$ 中字典序最小的。
题解
考虑贪心，假设现在字符串为 $s_{L}s_{L+1}\cdots s_{R-1}s_R$，显然选取 $S_L,S_R$ 中字典序最小的最优。
如果 $S_L=S_R$，接下来考虑选择 $S_{L+1},S_{R-1}$ 中字典序最小的，直到比较到端点为止。
上述操作等价于比较 $S[L,n]$ 和 $S[1,R]$ 的字典序。考虑构造字符串 $s_1s_2\cdots s_n+\text{\0}+s_n\cdots s_2s_1$。
于是可以通过后缀数组得到 $S[L,n]$ 和 $S[1,R]$ 的排名，时间复杂度 $O(n\log n)$。
