原理

先说后缀排序

定义：

(sa[i]:) 排名为(i)的后缀的位置

(rak[i]:) 从第 (i) 个位置开始的后缀的排名，下文为了叙述方便，把从第(i)个位置开始的后缀简称为"后缀(i)"

(tp[i])：第二关键字排名为 (i) 的下标

(tax[i])：(i)号元素出现了多少次，基数排序的桶

（构造后缀数组还有DC3算法（三分？）和建后缀树，跑dfs序的两种(O(n))做法，但是常用的是后缀排序）

观察易得，(rk) 和 (sa) 是个互逆的数组，也就是 (rk[sa[i]]=i,sa[rk[i]]=i)

如果直接sort会爆掉复杂度，因为我们的字符串长度和比较的时候复杂度和长度相关

所以我们就对每一位做文章

先是基数排序，把所有的后缀按照第一位的字符排个序

然后考虑倍增

然后比较巧妙的一步就是在于“(i)号后缀的前(frac{w}{2})个字符形成的字符串是(i-) (frac{w}{2})号后缀的后(frac{w}{2})个字符形成的字符串”

这里大概需要意会我们去掉了后缀(i)的后面部分

我们每一次执行循环中的内容的时候有一个部分排好序的后缀数组（可以意会的）

这里每一次考虑倍增新出来的那些位数，对它们进行基数排序就可以了

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define reg register
namespace yspm{
    inline int read(){
        int res=0,f=1; char k;
        while(!isdigit(k=getchar())) if(k=='-') f=-1;
        while(isdigit(k)) res=res*10+k-'0',k=getchar();
        return res*f;
    }
    const int N=1e6+10;
    int sa[N],rk[N],ton[N],sec[N],n,m,h[N];
    char s[N];
    inline void gb(){
        memset(ton,0,sizeof(ton));
        for(reg int i=1;i<=n;++i) ton[rk[i]]++;
        for(reg int i=1;i<=m;++i) ton[i]+=ton[i-1];
        for(reg int i=n;i>=1;--i) sa[ton[rk[sec[i]]]--]=sec[i];
        return ;
    }
    signed main(){
        scanf("%s",s+1); n=strlen(s+1);
        m=75; for(reg int i=1;i<=n;++i) rk[i]=s[i]-'0'+1,sec[i]=i; gb();
        for(reg int w=1,p=0;p<n;m=p,w<<=1){ 
            p=0; for(reg int i=1;i<=w;++i) sec[++p]=n-w+i;
            for(reg int i=1;i<=n;++i) if(sa[i]>w) sec[++p]=sa[i]-w;
            gb(); swap(rk,sec); rk[sa[1]]=p=1;  
            for(reg int i=2;i<=n;++i){
                if(sec[sa[i]]==sec[sa[i-1]]&&sec[sa[i]+w]==sec[sa[i-1]+w]) rk[sa[i]]=p; else rk[sa[i]]=++p;
            } 
        }
        int k=0;
        for(reg int i=1;i<=n;++i){
            if(rk[i]==1){h[1]=k=0; continue;}
            int j=sa[rk[i]-1];
            if(k>0) --k; while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) ++k;
            h[rk[i]]=k;
        } 
        for(reg int i=1;i<=n;++i) printf("%lld ",h[i]); puts("");
        return 0;
    }
}
signed main(){return yspm::main();}

然后后缀数组比较重要的是 (h) 数组和 (height) 数组

[height[i]=LCP(sa[i-1],sa[i]) ]

(height) 数组有以下性质：

若两个下标 (j,k) 满足 (rk_j<rk_k)

那么(LCP(j,k)=minlimits_{l=rk[j]+1}^{rk[k]} height_l)

这个感觉就比较有用了

然而不太好求

再定义：(h_i=height[rk_i])

然后 (h) 数组有以下性质：

[h_ige h_{i-1}-1 ]

关于上面两条性质的证明？link

运用 (h) 数组的性质，我们就可以在较低复杂度内暴力计算出 (h,height)

例题

(Suffix Array) 求本质不同的子串个数的方法：

求出来 (sa) 和 (height) 数组，然后

[ans=sum _ {i=1}^n n+1-sa_i-height_i ]

后缀数组求任意子串 (lcs) 的方法：

把原串逆过来复制一次放到原串末尾（中间要添加字符的）

然后就又变成了 (lcp) 问题

求一些后缀的 (lcp) 和的问题

（好像可以用后缀虚树，即 (bzoj SvT) 一题的全称就是 (Suffix virtual Tree) ，那题目直接搞个树然后每次按照消耗战的做法做就行了）

用后缀数组就单调栈就好了

套路题小结

(1.) 二分 (rk) 或者下标

(JSOI2015) 串分割中，观察到相关的性质，减少枚举量，然后二分得解

(HEOI2016) 字符串中，二分长度结合 (rmq) 及对 (rk) 用 (rmq) 或者主席树的维护实现最大 (lcp) 的查询

(2.) 差分

股市的预测和 Sandy 的卡片等题目中，题目涉及到趋势的询问，这时候差分再结合相应做法会比较巧妙

(3.) 两串的 (cdots)

考虑把第二个串复制一倍放到地一个后面，中间加入一个字典序大的字符进行维护

总的来看就是说后缀数组更多的是一个工具，具体还是要靠分析性质和结合二分，数据结构等手段对题目进行维护