后缀数组学习笔记

Author： RainAir
发布时间：March 21, 2019
1321views
One comment
4721 words
Categories：学习笔记

维基百科 - 后缀数组
让我们来看一下 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;
}

<h2>Height 数组</h2>

后缀数组如果只能排序的话~~那貌似没什么用~~，大多数后缀数组题目主要还是考察 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;
    }
}

<h4>求任意后缀的最大 lcp</h4>

$$lcp(x,y) = \min_{i=x}^y height_i$$
这东西随便维护一个区间极值就可以了，$O(1)$ 查询。

<h4>可重叠最长重复子串</h4>

意思是求最长的子串使得在字符串中重复出现过。
根据定义就是 height 数组中的最大值

<h4>不可重叠最长重复子串</h4>

POJ - 1743
我们来考虑二分答案。假设现在我们二分的答案是 $k$ ，想判断是否有 $>k$ 的符合题目要求的子串。
然后考虑在一些地方将 height 分开，保证每一段最小 $height \geq x$。分完组之后枚举一下看看长度是否满足存在不交的重复子串就可以了。

<h4>本质不同的子串数量</h4>

注意到子串 = 后缀的前缀。
对于排名为 $i$ 的后缀，它有 $n - sa_i + 1$ 个前缀，但是有 $height_i$ 个是和排名为 $i-1$ 的后缀的前缀相同的，减去就可以了。
所以答案就是
$$\sum_{i=1}^n (n-sa_i + 1-height_i)$$

Last modification：April 7th, 2020 at 10:14 pm

如果觉得我的文章对你有用，请随意赞赏

One comment

taozhiming
January 29th, 2023 at 08:56 am

/se，今天就要学这个了，可惜当时没给我们讲/kk

Reply

后缀数组学习笔记

RainAir • 2019 年 03 月 21 日

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

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

p = 0;
FOR(i,1,w) tp[++p] = N-w+i;
FOR(i,1,N) if(sa[i] > w) tp[++p] = sa[i]-w;

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;

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];
}

#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;
}

<h2>Height 数组</h2>

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;
    }
}

<h4>求任意后缀的最大 lcp</h4>

$$lcp(x,y) = \min_{i=x}^y height_i$$
这东西随便维护一个区间极值就可以了，$O(1)$ 查询。

<h4>可重叠最长重复子串</h4>

意思是求最长的子串使得在字符串中重复出现过。
根据定义就是 height 数组中的最大值

<h4>不可重叠最长重复子串</h4>

<h4>本质不同的子串数量</h4>

后缀数组学习笔记

One comment

Leave a Comment Cancel reply

NOI2021 退役记

I'm back

SDOI2020 退役记

点双连通分量 & 圆方树学习笔记

CSP2019 游记

无向图生成树计数

AC 自动机学习笔记

「优化」内存池

20联赛集训day6 题解

ARC118F Growth Rate

后缀数组学习笔记