后缀数组_牛客博客

定义

维基百科 - 后缀数组
让我们来看一下 wiki 上的定义：
在计算机科学里, 后缀数组（英语：suffix array）是一个通过对字符串的所有后缀经过排序后得到的数组。此数据结构被运用于全文索引、数据压缩算法、以及生物信息学。
令字符串 $S=S[1]S[2]...S[n]$ ， $S[i,j]$ 表示 $S$ 的子字符串，下标从 $i$ 到 $j$ 。

$S$ 的后缀数组 $A$ 被定义为一个数组，内容是 $S$ 的所有后缀经过字典排序后的起始下标。

满足 $\forall 1<i\leq n$ ,有 $S[A[i-1],n]<S[A[i],n]$ 。

求法

大体思想

这玩意可以使用倍增来求，当然也有常数比较大的 $O(n)$ 算法。
中心思想就是假设我们求出了考虑每个后缀前 $w$ 个的字典序，现在我们需要扩展到 $2w$ 的情形。首先 $w=1$ 的时候十分简单，就是对应的 ASCII 码。考虑每次 $w \times 2$ ，相当于要把每个后缀当做一个二元组来排序。我们考虑对于每个后缀指定两个变量 $rk$ 和 $tp$ ，目前考虑的长度下， $rk$ 指这个后缀的排名， $tp$ 指这个后缀后 $w$ 个字母的排名。显然 $tp$ 可以由上一轮的 $rk$ $O(n)$ 得到（后面会单独说）。然后我们就可以用上一轮的 $rk$ 和 $tp$ 当做二元组来排序，就能更新出这次的 $rk$ 了。
相信大家看完后肯定是一脸 mb，接下来我来详细的说一下算法过程。

算法过程

首先我们来定义一些变量： $sa_i$ 表示排名为 $i$ 的后缀的位置， $rk_I$ 表示第 $i$ 个后缀的排名， $tp_i$ 表示每次倍增里的第二关键字排名为 $i$ 的位置，我们设这个字符串 $s$ 的长度为 $n$ 。
首先按照定义，显然有

$\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(i,1,w) tp[++p] = N-w+i;
FOR(i,1,N) if(sa[i] > w) tp[++p] = sa[i]-w;

首先对于长度 $<w$ 的后缀，一定字典序会在前面，我们先都拿出来。
然后对于长度 $> w$ 的后缀，我们发现后缀 $i-w$ 的后 $w$ 个字符就是上一轮后缀 $i$ 的前 $w$ 个字符。（考虑这一轮 $2w$ 个字符的意义下）
所以代码就是按照上一轮的顺序从小到大枚举了每个长度 $> w$ 的后缀，然后找到第二关键字的对应位置定位过去即可。
之后我们搞个比较高效的排序（基数排序）排一下。
然后因为在这个倍增过程中可能有的后缀的 $rk$ 暂时相同，但是最后的答案一定是互不相同，于是我们需要对于这一轮的结果去一下重（重新分配 $rk$ 编号）

std::swap(tp,rk); // rk 没用了，当然这里最好写指针交换
rk[sa[1]] = p = 1;
FOR(i,2,N) rk[sa[i]] = (tp[sa[i-1]] == tp[sa[i]] && tp[sa[i-1]+w] == tp[sa[i]+w]) ? p : ++p;

去重的原理和上面的类似：如果前半段和后半段在上一轮的 $rk$ 相同的话那它们当前就是相同的。
然后就做完了。。。。
现在我们要解决的是找到一种高效的排序方法，首先显然你不能用 $O(nlogn)$ 排序，要不然和暴力就没区别了（可能还更慢）。
所以我们考虑 $O(n)$ 的基数排序。
先放一下代码：

inline void sort(){
    FOR(i,0,M) tax[i] = 0;
    FOR(i,1,N) tax[rk[i]]++;
    FOR(i,1,M) tax[i] += tax[i-1];
    ROF(i,N,1) sa[tax[rk[tp[i]]]--] = tp[i];
}

首先我们把桶清空，然后统计每种 $rk$ 的出现次数，然后做个前缀和（有助于快速查询排名）。
然后我们重点关注最后一句是在干什么。首先我们按第二关键字从大到小枚举（ $tp_i$ ），然后我们在找一下当前枚举的这个后缀的第一关键字排名（ $rk_{tp_i}$ ），然后由于是第二关键字从大到小枚举，所以目前的字符串排名一定是前半段相同的后缀中（当前 $rk$ 相同）最靠后的一个后缀，所以我们的前缀和就派上用场了。最后直接更新一下就可以了（排名是 $tax_{rk_{tp_i}}$ 的后缀是 $tp_i$ 号后缀）。
是不是很好理解？这样后缀数组就写完了。
附上 Luogu - 后缀排序的代码：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
#define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------\n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1000000+5;

char str[MAXN];
int N,sa[MAXN],tax[MAXN],M;
int pool1[MAXN],*rk = pool1,pool2[MAXN],*tp = pool2;

inline void sort(){
    FOR(i,0,M) tax[i] = 0;
    FOR(i,1,N) tax[rk[i]]++;
    FOR(i,1,M) tax[i] += tax[i-1];
    ROF(i,N,1) sa[tax[rk[tp[i]]]--] = tp[i];
}

inline void SuffixSort(){
    M = 75;
    FOR(i,1,N) rk[i] = str[i]-'0'+1,tp[i] = i;
    sort();
    for(int w = 1,p = 0;p < N;w <<= 1,M = p){
        p = 0;
        FOR(i,1,w) tp[++p] = N-w+i;
        FOR(i,1,N) if(sa[i] > w) tp[++p] = sa[i]-w;
        sort();
        std::swap(tp,rk);
        rk[sa[1]] = p = 1;
        FOR(i,2,N) rk[sa[i]] = (tp[sa[i-1]] == tp[sa[i]] && tp[sa[i-1]+w] == tp[sa[i]+w]) ? p : ++p;
    }
    FOR(i,1,N) printf("%d ",sa[i]);
}

int main(){
    scanf("%s",str+1);N = strlen(str+1);
    SuffixSort();
    return 0;
}

Height 数组

后缀数组如果只能排序的话~~那貌似没什么用~~，大多数后缀数组题目主要还是考察 Height 数组的性质。
首先扔一些定义。。。 $suf(i)$ 表示 $i$ 号后缀， $lcp(a,b)$ 表示后缀 $a$ 和 $b$ 的最长公共前缀。同时我们继续沿用上文的 $sa,rk$ 等定义。
定义 $height_i = lcp(sa_i,sa_{i-1})$
如果直接枚举后缀~~那还求后缀数组干嘛~~，所以说我们要考虑能否通过后缀数组求出的信息来线性推出 $height$ 。
对于 $height$ 数组有性质 $height_{rk_{i}} \geq height_{rk_{i-1}}-1$ 。证明就不证了（笔者太菜不会，其实分类讨论一下就可以了）。
代码：

inline void get(){
    int j,k = 0;
    FOR(i,1,N){
        if(k) --k;
        int j = sa[rk[i]-1];
        while(str[i+k] == str[j+k]) ++k;
        height[rk[i]] = k;
    }
}