后缀数组

定义

令字符串 (S=S[1]S[2]S[3]...S[n]) ，(S[i,j]) 表示下标从(i) 到 (j) 的字串
(S)的后缀数组(A)被定义为一个数组，内容是 (S)的所有后缀经过字典排序后的起始下标。
即(A[i]) 表示排名第几的后缀的起始下标
显然 (forall 1<ileq n)，(S[A[i-1],n]<S[A[i],n])。
首先我们定义一些变量：(sa_i) 表示排名为 (i) 的后缀的位置，(rk_i) 表示第i个后缀的排名，(tp_i) 表示每次倍增里的第二关键字排名为 (i) 的位置（下面会提到），我们设这个字符串长度为n

求法

大体思想

其实中心思想就是通过倍增来求
假设我们求出了考虑每个后缀前(w) 个的字典序，现在要扩展到(2w) 的情况。，考虑(w imes 2) 相当于把每个后缀当二元组来排序。我们假定两个变量 (rk) 和 (tp) ，在目前长度(w) 下，(rk) 指这个后缀的排名，(tp)指这个后缀后 (w) 个字母的排名。这样我们就可以用上一轮的 (rk) 和 (tp) 当做二元组来排序，就能更新出这次的rk了。
结合这张经典的过程图来理解：

算法过程

首先，按照定义，显然有

[forall i in [1,n]，sa_rk_i = rk_sa_i = i ]

也就是说这两个数组可以 (O(n)) 互推。
开始时(w = 1) 我们拿来排序的的二元组是 ((s_i,i)) ，显然ASCII码小的会在前面。然后我们开始倍增。已经求出了长度为 (w) 的答案，考虑去更新 (2w) 的答案。
现在我们来看如何求(tp) 。代码如下：

     p=0;
     for(int i=1;i<=w;i++) tp[++p]=n-w+i;
     for(int i=1;i<=n;i++) if(sa[i]>w) tp[++p]=sa[i]-w;

由上图可以对于长度(< w) 的后缀，其字典序一定出现在前面，我们都先拿出来。
然后对于长度 (> w)的后缀，可以发现后缀 (i - w) 的后 (w) 个字符就是上一轮后缀 (i) 的前 (w) 个字符（本轮长度为 (2w) 上一轮为 (w) ）。
之后用个高效率（(because) 只有两个关键字）的排序（(O(n)) 基数排序）搞一下就行了。

    void Rsort()
    {
	for(int i=0;i<=m;i++) tax[i]=0;
        for(int i=1;i<=n;i++) tax[rk[i]]++;
        for(int i=1;i<=m;i++) tax[i]+=tax[i-1];
	for(int i=n;i;i--) sa[tax[rk[tp[i]]]--]=tp[i];
    }

(tax) 数组辅助记录每个 (rk) 的个数，求前缀和便于快速查询排名。
我们重点关注最后一句是干嘛的。首先我们按第二关键字 (tp_i)从大到小枚举，然后找这个后缀第一关键字的排名（(rk_ {tp_{i} })），这个时候前缀和就用上了，因为是从大到小枚举，我们直接把他插入到相应排名的最后。
排名 (tax_{rk_{tp_i}}) 的后缀是 (tp_i) 号的后缀
~~看不懂没关系，一定要参考定义！！！一开始我也没懂~~
最后，排序产生的的 (rk) 一定是互不相同的，但是在倍增过程中可能有的后缀(rk) 暂时相同，所以我们要对排序的结果去一下重，重新分配 (rk)

     swap(tp,rk);//上一轮的rk已经没用了，用tp存一下
     rk[sa[1]]=p=1;
     for(int i=2;i<=n;i++) rk[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w]?p:++p);

去重原理同上，如果前半段和后半段在上一轮的rk里相同，那么本轮就相同。
附上完整的代码:

//#pragma GCC optimize(2)
//#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int N=1.5e6+5;
const ll mod=998244353;
const int base=7e5;
const double eps=1e-5;
const double pi=acos(-1);

#define ls p<<1
#define rs p<<1|1
char s[N];
int n,rk[N],sa[N],tp[N],m,tax[N];
int height[N];
void Rsort()
{
    for(int i=0;i<=m;i++) tax[i]=0;
    for(int i=1;i<=n;i++) tax[rk[i]]++;
    for(int i=1;i<=m;i++) tax[i]+=tax[i-1];
    for(int i=n;i;i--) sa[tax[rk[tp[i]]]--]=tp[i];
}
void suffix()
{
    m=75;
    for(int i=1;i<=n;i++) rk[i]=s[i]-'a'+1,tp[i]=i;
    Rsort();
    for(int w=1,p=0;p<n;w<<=1,m=p)
    {
        p=0;
        for(int i=1;i<=w;i++) tp[++p]=n-w+i;
        for(int i=1;i<=n;i++) if(sa[i]>w) tp[++p]=sa[i]-w;
        Rsort();
        swap(tp,rk);
        rk[sa[1]]=p=1;
        for(int i=2;i<=n;i++) rk[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w]?p:++p);
    }
    int k=0;
    for(int i=1;i<=n;i++)
    {
        if(k) --k;
        int j=sa[rk[i]-1];
        while(s[i+k]==s[j+k]) ++k;
        height[rk[i]]=k;
    }
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>(s+1);n=strlen(s+1);
    suffix();
    for(int i=1;i<=n;i++) printf("%d ",sa[i]);
    return 0;
}

Height数组

后缀数组如果真能排序的话好像没什么用，大部分题目考察的还是height数组的应用。
首先还是定义，(lcp(a,b)) 表示后缀 (a) 和 (b) 的最长公共前缀。
(height_i = lcp(sa_i,sa_{i-1}))
我们考虑通过上面得到的信息来求 (height) （~~要不写那么多干嘛~~）
代码：

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

经典应用

求任意后缀的 (lcp)

[lcp(x,y) = min_{i=rk[x]+1}^{rk[y]} height_i ]

随便拿个数据结构维护一下就可以了。

可重叠最长重复子串

就是求最长的子串，使得在 (S) 中至少出现两次
显然就是 (height) 数组的最大值

本质不同的子串数量

子串 = 后缀的前缀
对于一个长度为 (i) 后缀，它有 (n - sa_i + 1) 个前缀，但是每个后缀有 (height) 个与 (rk_{i-1}) 重复，减去即可。
所以 (ans =)

[frac{n(n+1)} {2}-sum_{i=1}^{n}height_{i} ]