后缀数组（SA）

本文参考 OI Wiki。

后缀数组（Suffix Array）主要关系到两个数组：\(sa\) 和 \(rk\)。

我们称后缀 \(i\) 表示后缀 \([i,n]\)。

其中 \(sa_i\) 表示排名为 \(i\) 的后缀是什么，\(rk_i\) 表示后缀 \(i\) 的排名。\(sa\) 和 \(rk\) 是互逆的。

字符串比较规则是逐位比较，空位小于任何字符。

O(n^2 \log n) 朴素做法

对所有后缀 sort 即可，一次 compare 是 \(O(n)\) 的。

O(n \log^2 n) 倍增做法

首先对字符串所有长度为 \(1\) 的子串排序，复杂度 \(O(n\log n)\)，这样我们就得到了所有长度为 \(1\) 的字符串的排序和排名。编号为 \(i\) 的子串排名为 \(rk_i\)。

然后对长度为 \(2\) 的子串排序，我们不比较 \(\{s_i,s_{i+1}\}\) 和 \(\{s_j,s_{j+1}\}\) 的大小，而是比较 \(\{rk_i,rk_{i+1}\}\) 和 \(\{rk_j,rk_{j+1}\}\)。时间复杂度也是 \(O(n \log n)\)。更新编号为 \(i\) 的子串的 \(rk\)。

然后对长度为 \(4\) 的子串排序，我们不对长度为 \(4\) 的子串逐位比较，而是比较 \(\{rk_i,rk_{i+1}\}\) 和 \(\{rk_j,rk_{j+1}\}\)。时间复杂度也是 \(O(n \log n)\)。

以此类推，一共做 \(\log n\) 次，所有总时间复杂度 \(O(n\log^2n)\)。

O(n \log n) 倍增基数排序做法

每次排序要对二元组 \(\{first,second\}\) 排序。因为二元组的值域都在 \([1,n]\) 里，所以考虑基数排序。

就是先对第二关键字进行计数排序，注意可能有排名并列的子串哦。然后从小到大扫描桶，放到以第一关键字为下标的另一组桶里面，这样就可以保证第一关键字相等的子串，在桶里面的顺序会按照第二关键字有序啦。

常数优化

OI Wiki 说，直接写在 LOJ 上面会被卡常。

第二关键字无需计数排序

左边的部分子串的第二关键字的排名就是 \(rk\)，没有变的，只是右边有一部分的子串，它们的第二关键字是个空串，需要把它们全部排到前面。

优化计数排序的值域

每次对 \(rk\) 进行更新之后，我们都计算 \(rk\) 的值域。这样下一次计数排序就不用扫那么多桶了。

若排名都不相同可直接生成后缀数组

如果新的 \(rk\) 数组值域在 \([1,n]\)，那么就不需要继续排了，排名已经确定了。

模板题 code

P3809 【模板】后缀排序

#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
namespace SA {
    constexpr int N=1e6+7;
    char s[N];
    int n,m,p;
    int rk[N],sa[N];
    int tmprk[N];
    int cnt[N];
    int id[N];
    void main() {
        sf("%s",s+1);
        n=strlen(s+1);
        m=128;
        rep(i,1,n) cnt[rk[i]=s[i]]++;
        rep(i,1,m) cnt[i]+=cnt[i-1];
        per(i,n,1) sa[cnt[rk[i]]--]=i;
        for(int w=1;;w<<=1,m=p) {
            int cur=0;
            rep(i,n-w+1,n) id[++cur]=i;
            rep(i,1,n) if(sa[i]>w) id[++cur]=sa[i]-w;
            memset(cnt,0,sizeof(cnt));
            rep(i,1,n) cnt[rk[i]]++;
            rep(i,1,m) cnt[i]+=cnt[i-1];
            per(i,n,1) sa[cnt[rk[id[i]]]--]=id[i];
            p=0;
            memcpy(tmprk,rk,sizeof(rk));
            rep(i,1,n) {
                if(tmprk[sa[i]]==tmprk[sa[i-1]] && tmprk[sa[i]+w]==tmprk[sa[i-1]+w]) rk[sa[i]]=p;
                else rk[sa[i]]=++p;
            }  
            if(p==n) break;
        }
        rep(i,1,n) pf("%d ",sa[i]);
    }
}
int main() {
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("my.out","w",stdout);
    #endif
    SA :: main();
}

height 数组

\(height_i = lcp(sa_{i-1},sa_i),height_1 = 0\)。

引理：\(height_{rk_i} \ge height_{rk_{i-1}}-1\)。不证。不会证。

那 \(height\) 数组就好求了。直接搬 OI Wiki 的代码上来。

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

\(height\) 数组用来求任意两个后缀的最长公共前缀。

有 \(lcp(sa_i,sa_j)=\min_{k=i+1}^j\{height_k\}\)。证明略，感性理解好吧。

更多应用详见 OI Wiki。

经验

P1117 [NOI2016] 优秀的拆分

题意：给你一个长度为 \(n\) 的字符串，问有把所有子串划分成 \(AABB\) 的形式的方案数之和。\(A,B\) 非空。

思路：只需要找到所有的 \(AA\)，在 \(AA\) 末尾记录个数，找到所有 \(BB\)，在 \(BB\) 开头记录个数，然后枚举 \(AA,BB\) 分割点相乘方案数即可。

如何找 \(AA\)？枚举 \(len=|A|\)，将 \(x=klen\) 看做关键点，显然 \(AA\) 一定会覆盖恰好两个关键点。而且由于关键点的间隔是 \(len\)，所以必须满足 \(s_{i\times len}=s_{j\times len}\)。当然也有 \(s_{i\times len\pm q}=s_{j\times len\pm q}\) 也需要相等。

于是我们对所有相邻的关键点 \(i,i+1\)，求以这两个点为末尾的 LCP（最长公共前缀）和以这两个点为开头的 LCS（最长公共后缀）。然后就有一段区间里面的 \(AA\) 都是合法的。因为要在 \(AA\) 的末尾贡献答案，所以是做区间加，可以差分变成单点加。

其中这个 LCP 和 LSP 都可以使用 \(height\) 数组 \(O(1)\) 求。根据调和级数 \(\sum \frac{n}{i}=O(n \log n)\)，以及预处理后缀数组的时间，总时间复杂度 \(O(n \log n)\)。