后缀数组的相关概念

后缀数组： 对于一个长度是 $n$ 的字符串，存在 $n$ 个不同的后缀，称第 $i$ 个字符为起点的后缀为第 $i$ 个后缀，则后缀数组能将所有后缀从小到大进行排序。

后缀数组有两种实现方法，分别是倍增法和 $DC3$，倍增法的时间复杂度为 $O(nlogn)$，但是常数较小，$DC3$ 的时间复杂度为 $O(n)$，但是常数较大。

后缀数组能处理出几个常用信息，然后用这些信息来解决问题，$sa_i$ 记录排名第 $i$ 位的是第几个后缀，$rk_i$ 记录第 $i$ 个后缀的排名是多少，$height_i$ 记录第 $sa_i$ 个后缀和第 $sa_{i-1}$ 个后缀的最长公共前缀。

后缀数组的原理

由于倍增法常数较小，且思路清晰，比较常用，因此这里只讲解倍增法的后缀数组，可以自行学习 $DC3$ 的后缀数组。

倍增法的思路就是每次倍增的对某些后缀排序，直到所有后缀都排好序为止。

首先将所有后缀以第一个字符为关键字进行排序，如果某两个后缀的关键字相同，则相对顺序不变。这里用基数排序来为所有后缀进行排序，基数排序能在 $O(n)$ 的时间复杂度之内将所有字符串排序（没学过基数排序的同学后面会稍作讲解）。

此时所有后缀都按照第一个字符排好序，然后再去进行倍增。假设当前所有后缀已经按照前 $k$ 个字符排好序（如果某个后缀不足 $k$ 个字符则在后面补上空字符，空字符最小）。现在我们已经考虑了前 $k$ 个字符，接下来我们就要考虑前 $2k$ 个字符，倍增的去考虑。

我们将每个后缀的前 $k$ 个字符当作第一关键字，将每个后缀的第二段 $k$ 个字符当作第二关键字。然后将所有后缀按照这两个关键字进行排序，如果第一关键字更大，则字符串更大。如果第一关键字相同，则第二关键字大的字符串更大，这样就将所有字符串按照前 $2k$ 个字符排序。而每一轮排序之后我们都会将前 $k$ 个字符进行离散化，因此第一关键字是一个整数，而第二个关键字我们也会通过一些处理给他变成一个整数。由于只有 $n$ 个后缀，因此离散化后的数是在 $1 \sim n$ 的范围内的，这样的排序同样可以用基数排序来排，也是 $O(n)$ 的时间复杂度。

通过以上思路，每次考虑的字符数量是倍增的，因此最多执行 $logn$ 次，就可以考虑到 $n$ 个字符，就能将所有后缀排序。每次排序是 $O(n)$ 的复杂度，因此整个的时间复杂度就是 $O(nlgn)$。

到此，就是后缀数组的大致思路，接下来还有一些细节需要考虑。首先对于基数排序，它的前提是每个数需要在 $1 \sim n$ 以内，不能比 $n$ 大，因为基数排序的时间复杂度是和值域有关的，因此值域不能太大，所以这里才需要用离散化。

基数排序的思路，先求一下 $1 \sim n$ 中每个数 $i$ 出现的次数 $c_i$，然后再对于每个 $i$ 求一下 $\leq i$ 的数的个数 $s_i$，显然就是求一个前缀和，然后我们从前往后依次看每个数 $a_i$，如果 $\leq a_i$ 的数的个数是 $x$，则 $a_i$ 的排名就是 $x$，此时第 $x$ 个位置已经有数了，此时 $\leq a_i$ 的数还剩 $x-1$ 个，都应该放在 $x$ 的前面，因此令 $s_{a_i} - 1$，然后再依次往后看剩下的每个数 $a_j$，根据 $\leq a_j$ 的数的个数来确定他的排名，同时更新 $s$ 数组，最终就能确定出每个数的排名。

这里有一个基数排序的特性，就是对于 $a_i$，我们是根据 $s_{a_i}$ 来确定他的排名，此时如果存在两个 $a_i$，则第二个 $a_i$ 将会排在 $s_{a_i}-1$ 的位置，也就是倒着排序。这会导致排序后相同数之间的相对顺序发生改变，但是我们后缀数组中要保证相同数之间的相对顺序不变，这里要想保证不变也非常简单，只需要在奇数排序的过程中从后往前依次确定每个数的位置，这样就会令第二个 $a_i$ 排在后面，第一个 $a_i$ 排在前面，保证相同数之间的相对顺序不变。

以上是基数排序单关键字的排法，而双关键字排序则是类似的，只需要先将所有后缀按照第二关键字排好序，再将所有后缀从后往前按照第一关键字排序，此时既能保证所有后缀都按照双关键字排好序，又能保证相同后缀之间的相对顺序不变。

这里还需要考虑如何将后缀按照第二关键字排序，可以发现对于第 $i$ 个后缀的第二关键字刚好对应第 $i+k$ 个后缀的第一关键字，因此对于第 $i$ 个后缀在第二关键字中的排名，其实就是第 $i+k$ 个后缀在第一关键字中的排名 $-k$，直接递推即可。另外，第 $n-k+1$ 个后缀及以后的所有后缀，长度都是 $\leq k$ 的，因此他们的第二关键字都是补空字符的，因此他们在第二关键字排序中一定是最小的 $k$ 个后缀，且相对关系没有变化，因此这 $k$ 个后缀的排名可以直接得到。到此就能将所有后缀按照第二关键字排序，接着再去进行后续处理即可。

然后每次排序完之后需要将前 $2k$ 个字符作为下一轮排序的第一关键字进行离散化，这里的离散化也比较简单，如果当前后缀的前 $2k$ 个字符和前一个后缀的前 $2k$ 个字符相同，则离散化后的排名相同，否则比前一个后缀的排名 $+1$，直接枚举处理即可。

排序的结束标志就是离散化后最后一个后缀的排名是不是 $n$，如果是 $n$ 说明已经将 $n$ 个后缀完全区分开了，则排序结束。否则一定还存在某两个后缀排名相同，则需要继续排序。这里由于每个后缀的长度各不相同，因此所有后缀一定不可能相同，即排名不可能相同。

至此我们将所有后缀排好序。然后还需要预处理出 $height$ 数组。$height_i$ 表示排名第 $i$ 的后缀和排名第 $i-1$ 的后缀的最长公共前缀。

我们设 $lcp(i, j)$ 表示排名第 $i$ 的后缀和排名第 $j$ 的后缀的最长公共前缀。

首先两个后缀的最长公共前缀和两个后缀的顺序是无关的，因此 $lcp(i, j) = lcp(j, i)$，并且 $lcp(i, i) = len(i)$。除此以外，还有一个关键的性质，$lcp(i, j) = min\big( lcp(i, k), lcp(k, j) \big)~~k\in [i,j]$，这里保证 $i < j$，否则可以将 $i, j$ 交换。

当 $lcp(i, k) \leq lcp(k, j)$ 时，显然 $lcp(i, j) \geq min\big( lcp(i, k), lcp(k, j) \big)$，反之也同理。

因此首先能保证 $lcp(i, j) \geq min\big( lcp(i, k), lcp(k, j) \big)$。

假设 $lcp(i, j)$ 长度为 $x$，则此时排名第 $i$ 个后缀的前 $x$ 个字符和排名第 $j$ 个后缀的前 $x$ 个字符相等，此时由于排名第 $i$ 的后缀 $\leq$ 排名第 $k$ 的后缀 $\leq$ 排名第 $j$ 的后缀，因此排名第 $i$ 个后缀的前 $x$ 个字符 $\leq$ 排名第 $k$ 个后缀的前 $x$ 个字符 $\leq$ 排名第 $j$ 个后缀的前 $x$ 个字符。又因为 $lcp(i, j)$ 的长度为 $x$，因此排名第 $k$ 个后缀的前 $x$ 个字符和排名第 $i$ 个后缀的前 $x$ 个字符和排名第 $j$ 个后缀的前 $x$ 个字符都相等。因此 $lcp(i, j) \leq min\big( lcp(i, k), lcp(k, j) \big)$

综上所述，证明 $lcp(i, j) = min \big( lcp(i, k), lcp(k, j) \big)$

利用这个性质我们就能将任意的 $lcp(i, j)$ 进行拆分，即 $lcp(i, j) = min\lbrace lcp(i, i+1), lcp(i+1,i+2),…,lcp(j-1,j) \rbrace$。

此时 $height_i$ 其实就是 $lcp(i-1,i)$。接下来就要考虑去求 $lcp(i-1,i)$。这里还要用另一个重要的性质。

设 $h_i = height_{rk_i}$，即第 $i$ 个后缀和排名在它前面一位的后缀的最长公共前缀。（注意第 $i$ 个后缀和排名第 $i$ 个后缀的区别）这里的性质就是 $h_i \geq h_{i-1}-1$。

对于第 $i$ 个后缀，第 $i-1$ 个后缀可能排在第 $i$ 个后缀的前面，也可能排在它的前面，我们不妨设第 $i-1$ 个后缀排在第 $i$ 个后缀前面。假设排名在第 $i-1$ 个后缀前面一位的后缀是第 $k$ 个后缀，

然后分情况讨论，如果第 $k$ 个后缀和第 $i-1$ 个后缀的首字符不相同，也就是第 $k$ 个字符和第 $i-1$ 个字符不相同，则 $h_{i-1} = 0$，$h_{i-1}-1=-1$，此时 $h_i$ 显然大于 $-1$。

如果第 $k$ 个后缀和第 $i-1$ 个后缀的首字符相同，也就是第 $k$ 个字符和第 $i-1$ 个字符相同，那么继续从第 $k+1$ 个字符和第 $i$ 个字符往后看，也就是第 $k+1$ 个后缀和第 $i$ 个后缀，由于第 $k$ 的后缀的排名在第 $i-1$ 个后缀的前面，所以第 $k+1$ 个后缀的排名也应该在第 $i$ 个后缀的前面，我们假设第 $k+1$ 个后缀在第 $i$ 个后缀的前面，在第 $i-1$ 个后缀的后面，此时第 $k+1$ 个后缀和第 $i$ 个后缀的最长公共前缀就应该等于第 $k$ 个后缀和第 $i-1$ 个后缀的最长公共前缀再去掉第一个字母，此时第 $k+1$ 个后缀和第 $i$ 个后缀的最长公共前缀就应该是 $h_{i-1}-1$，而第 $k+1$ 个后缀和第 $i$ 个后缀之间又加了若干个后缀，假设第 $i$ 个后缀的前面一位是第 $x$ 个后缀，根据前面的性质，我们知道 $lcp(k+1, i) = min\big( lcp(k+1,x), lcp(x, i) \big)$，因此就有第 $x$ 个后缀和第 $i$ 个后缀的最长公共前缀 $\geq$ 第 $k+1$ 个后缀和第 $i$ 个后缀的最长公共前缀，也就是 $h_i \geq h_{i-1}-1$。

综上所述，证毕。

有了这个性质之后就可以有一个 $O(n)$ 的做法，我们可以从前往后枚举每个后缀，假设现在已经求完了 $h_{i-1}$，那么对于 $h_i$，由于 $h_i \geq h_{i-1}-1$，所以我们不用从第一个字符开始枚举来求 $h_i$，我们可以直接从第 $h_{i-1}-1$ 个字符开始枚举。这样就会保证我们枚举的数量是非常有限的，只有 $O(n)$ 的级别。

以上就是倍增法的后缀数组的全部思路以及一些细节上的处理，可以发现中间的证明比较复杂，但是整体思路还是比较清晰的。是一个非常巧妙的数据结构。