后缀数组

摘要

后缀数组由 Manber & Myers 在 1990 年首先提出《Suffix arrays: a new method for on-line string searches》,用以替代后缀树,并且改进了存储空间的需求。

好吧本该是 2019.6.16 编入精选文章的,但太难复习了于是声名一下,是个半成品

概述

所以后缀数组到底是什么神仙玩意儿?

VFK 曾经说过:“NOI 试机的时候,有很多选手都在照着书打后缀数组,因为不理解。”

好的所以你知道这个东西大概有多懵逼了。后缀数组往往花大概十几分钟就能理解算法。

诶不是说不理解吗 emm

其实,不理解的是代码。

好的我们不了,干正事。

一句话说,后缀数组(Suffix Array)是一个串的所有后缀按照字典序排列形成的指针数组。

我们解释一些标记:

  1. 字符串以 1 为起点。
  2. 表示以第 i 个元素开头的后缀。
  3. 表示字典序从小到大排名为 i 的后缀的标号。
  4. 表达第 i 个后缀的排名。

举一个例子吧。

考虑字符串 banana:

i    : 1 2 3 4 5 6
s[i] : b a n a n a

对应的后缀数组如下:

suf[1]:banana
suf[2]:anana
suf[3]:nana
suf[4]:ana
suf[5]:na
suf[6]:a

按字典序排序

suf[6]:a
suf[4]:ana
suf[2]:anana
suf[1]:banana
suf[5]:na
suf[3]:nana

则后缀数组为

i   : 1 2 3 4 5 6
sa[i]:6 4 2 1 5 3

表示字典序排第 i 个的后缀的首字母下标

则每一个后缀对应排序后的位置为:

i    :1 2 3 4 5 6
rk[i]:4 3 6 2 5 1

表示下标为 i 的后缀的排名。

好的。上述概念建议大家牢记哦。不然后面会不知所措的

构造后缀数组

为了给大家一个循序渐进的理解过程,我决定(扯一点废话)为大家细致讲解这其中的种种前因后果。

后缀数组的关键在于 sa 和 rk

首先,我们有一个朴素算法:直接对后缀排序,复杂度 .

事实上,构造后缀数组可以通过桶排序 + 倍增,复杂度 .

也有线性的算法,如 DC3 和 SA-IS 算法。

今天我们讲 的算法。为什么呢?泥萌可以用头想一想这个问题。

概括原理

如果我们已知每一个后缀,长度为 的前缀的 sa 和 rk,那么我们可以在 O(n) 时间内推导出长度为 2j 的 sa 和 rk。每次 j 倍增,即可在 时间内求出后缀数组。

不知道做为神仙奆奆的读者看懂没?反正我是没打算写出来让人看懂的

我们用这个叫作 Windows 画图的OIer 必备的主流像素涂鸦与图像编辑软件为大家献上灵魂讲解。

算法图解

倍增桶排算法的实质就是排序。但是这是有技巧的排序,因此可以降低复杂度。看名字就知道,该算法利用了桶排序。不过我们知道排序是有关键字的。这就倍增所做的事情。

整体上讲,我们通过不断更改关键字做排序,通过不同的关键字对元素排序。而桶排序是稳定的,这意味着我们可以利用若干个不同的关键字对数组的局部特征排序。所有的关键字必然覆盖到整个数组的特征。那么多次局部排序后,就完成了整体的排序。

倍增是指关键字的倍增。算法一共做 k 次桶排序。第 j 次排序的关键字是每个后缀的长度为 的前缀。即我们按照长度为 的前缀的字典序排序。需要注意的是,这其中极有可能出现相同的前缀(即相同的关键字)。这时就要求我们在同一关键字的桶中保留他们在排序前的相对顺序。这一点桶排序能做到。

好的我瞎扯了一会儿,估计大家还是没怎么看懂 emm 我们还是举一个例子吧。

考虑字符串 banana。

j=0

首先,我们可以初始化 rk 的值。对于 j=0 的情况,后缀的排名相当于是第一个字符的字母表序号。于是可以看到在 j=1 緑色框框中,初始化的 rk 为 .

j=1

对于 j=1 的情况,相当于我们要对上述 rk 排序。前缀倍长,我们可以利用上次计算的 rk 的结果,直接取往后第 个后缀的 rk 值。这样就形成了一些二元组(j=1 緑色框框第二行的序列)。注意到最后一个后缀的后面没有后缀,因此其第二关键字为 0。对二元组桶排序。第一关键字为第一元,第二关键字为第二元。我们将它理解为,先按前 个排序;如果相等,再按后 个排序。

于是我们对这个二元组求排名即可。这就得到了 j=2 的緑色框框中的第一行序列。

SuffixArray.png

j=2

再倍长前缀,意味着我们要找到往后第 个后缀的 rk 值作为第二关键字。然后就形成了 j=2 的第二行的二元组。注意到这个二元组序列的最后两个是没有第二关键字的。对这个二元组排序,得到 j=4 的第一行的序列。

j=3

接下来也不用我说了,找到往后第 个后缀的 rk 做第二关键字,排序即可。

这样就得到了我们要求的 rk 数组。

理解上去毫无压力对吧?如果你直接模拟这个二元组桶排的过程,是可以很好地完成算法的。然而这样写常数似乎有点大(我没写过

于是,当你打开各个大佬博客中的《后缀数组模板》之类的文章后,你对着代码就开始纠结了 emm

背板要素

后缀数组的板子,笔者认为十分难背。这里笔者整理一下后缀数组模板的要素帮助背板

变量: ,数组 .

桶排序:排序对象是 ,排序关键字是 。(相对保持不变的关键字为 ).

初始化: .

第一次:当做步长为 0,那么一二关键字重合,所以 则由字符决定, 求得

倍增:

  1. ,按第二关键字排列 在过程中可能重复,但 中的元素不会重复);
  2. ,按第一关键字给 排序(桶排序);
  3. ,用旧的 配合 求新的 (交换的技巧)

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;

namespace SA{
    int l;// 字符串长度,1 起点
    int sa[N],rk[N];
    int t[N],bin[N],sz;//sz: 桶的大小
    void qsort(){// 桶排序
        for(int i=0;i<=sz;i++)bin[i]=0;
        for(int i=1;i<=l;i++)bin[rk[t[i]]]++;// 可以用 bin[rk[i]],用 bin[rk[t[i]] 可读性更强
        for(int i=1;i<=sz;i++)bin[i]+=bin[i-1];
        for(int i=l;i>=1;i--)sa[bin[rk[t[i]]]--]=t[i];
    }
    void make(char *s){
        l=strlen(s+1),sz=max(l,'z'-'0'+1);// 初始化 l,sz
        for(int i=1;i<=l;i++)t[i]=i,rk[i]=s[i]-'0'+1;// 初始化 t,rk(1 为最高排名)
        qsort();// 对 t 排序,结果转移到 sa 中
        for(int j=1;j<=l;j<<=1){// 开始倍增
            int tot=0;
            for(int i=l-j+1;i<=l;i++)t[++tot]=i;// 这些后缀没有第二关键字,因此排在最前面
            for(int i=1;i<=l;i++)if(sa[i]-j>0)t[++tot]=sa[i]-j;//{sa[i]-j} 按照第二关键字排列
            qsort();
            swap(t,rk);//t 变成上一次的 rk
            rk[sa[1]]=tot=1;
            for(int i=2;i<=l;i++)
                rk[sa[i]]=t[sa[i-1]]==t[sa[i]]&&t[sa[i-1]+j]==t[sa[i]+j]?tot:++tot;
        }
    }
}
char s[N];
int main(){
    scanf("%s",s+1);
    SA::make(s);
    for(int i=1;i<=SA::l;i++)printf("%d",SA::sa[i]);
    return 0;
}

首先要知道, 表示后缀的下标,并且取遍 中的元素。{t[i]} 数列满足后缀序列 是按字典序排列的,其中当 即为空串

也就是说, 是已经以第二关键字排好序的。而我们要完成的工作是这样的:把 以第一关键字(第一关键字就是前 个字符的字典序)排序,并保留第二关键字(第二关键字就是第 的字符串的字典序)的相对顺序不变。把排序的结果存储在

而我们的桶排序是一种稳定排序,因此使用桶排序时,同一个桶内的元素的相对顺序不会被打乱,也就保证了第二关键字的顺序

再看看我们的桶排序函数在干什么。把相同 的放在一个桶里面,这里的 ,不是 ,即我们以第一关键字为桶。我们没有模拟出二元组,那么我们是怎么实现二元组排序的呢?那就是,把第一关键字放在桶里面,然后按第二关键字的顺序拿出来!

什么叫按第二关键字的顺序?观察第三个循环的赋值,我们倒序枚举 i,即倒序遍历 ,然后减掉当前的桶的前缀和,这个前缀和就是当前 在排序后的的新的位置。也就是说,我们每一个桶内的元素也是倒着取出来的

别忘了桶内的元素是第一关键字,既然同一个桶内的第一关键字是一样的。桶的位置由其前缀和的差分决定(下标区间

同一个桶内的元素的顺序由第二关键字决定而我们是按第二关键字倒序的顺序来枚举对应的后缀下标,用这个下标的 找到其对应的第一关键字(即 ),也就是桶,然后在这个桶里面拿走末尾的下标。即我们倒着枚举倒着拿走,这等价于正着枚举正着拿走,那么就能够维护第二关键字的相对顺序

综上,采用这样的排序策略是正确的

排完序后就要统计新的 对应的 啦。怎么统计?这里当然是直接二元组比较啦。sa[i],sa[i-1] 是字典序相邻的两个后缀的下标,其对应的 就是上一次的 做了交换)。而 则是这两个下标后第 个下标,即第二关键字,对应的 就是第二关键字的

那么这就是 二元组啦,直接比较是否相同就好啦。另外, 不可能变小,只可能从相等变得更大(因为第一关键字排了序)

那个。。。上面的文字有点违和。那时我在忘了后缀数组后第二次理解算法时写的东西。

如果不好理解这玩意儿可以看看 神仙的 SA

模板题 LuoguP3809

Height&H 数组

利用后缀数组维护信息,需要一些辅助数组。

定义 表示 suf[i] 与 suf[sa[rk[i]-1]] 的最长公共前缀(LCP),也就是字典序排序后比 suf[i] 字典序小 1 的后缀与 suf[i] 的 LCP 的长度。

定义 ,即字典序排名第 i 个的后缀与他前一个后缀的 LCP 的长度。

举个例子吧

lz

大多数时侯我们用的是 height 数组。而为什么有一个 h 数组?因为这玩意儿好求。

结论一则: .

证明很显然,直接用 h[i-1] 的⽅案去掉头上的元素。因此我们只需要求 h 即可。

height 可直接索引 h 得到,构造 h 的代码如下:

int calc(int x,int y,int len){
    while(x+len<=l&&y+len<=l&&s[x+len]==s[y+len])++len;
    return len;
}
void calc_h(){
    for(int i=1;i<=l;i++)h[i]=(rk[i]==1)?0:calc(i,sa[rk[i]-1],max(h[i-1]-1,0));
}

均摊复杂度 .

那么,两个辅助数组有什么用呢?

后缀 LCP

我们可以用 height 求任意两个后缀的 LCP。因为我们知道字典序相邻两个后缀的 LCP,那么任意两个后缀的 LCP 就转化为 height 上的 RMQ 问题。ST 表预处理后可以做到 O(1) 查询。至于这个又有什么用见 NOI2016 优秀的拆分。

h 数组的模板见 SP609 和 SP705(双倍经验)

本质不同的子串个数:总数减掉height的和

一个完整的板子

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+5;

struct SA{
    char s[N];
    int l;
    int sa[N],rk[N];
    int t[N],bin[N],sz;
    int h[N],he[N];//h,height
    void qsort(){
        for(int i=0;i<=sz;i++)bin[i]=0;
        for(int i=1;i<=l;i++)bin[rk[t[i]]]++;
        for(int i=1;i<=sz;i++)bin[i]+=bin[i-1];
        for(int i=l;i>=1;i--)sa[bin[rk[t[i]]]--]=t[i];
    }
    void make(){
        l=strlen(s+1),sz=max(l,26);
        for(int i=1;i<=l;i++)t[i]=i,rk[i]=s[i]-'a'+1;
        qsort();
        for(int j=1;j<=l;j<<=1){
            int tot=0;
            for(int i=l-j+1;i<=l;i++)t[++tot]=i;
            for(int i=1;i<=l;i++)if(sa[i]-j>0)t[++tot]=sa[i]-j;
            qsort();
            swap(t,rk);
            rk[sa[1]]=tot=1;
            for(int i=2;i<=l;i++)
                rk[sa[i]]=t[sa[i-1]]==t[sa[i]]&&t[sa[i-1]+j]==t[sa[i]+j]?tot:++tot;
        }
    }
    int move(int x,int y,int len){
        while(x+len<=l&&y+len<=l&&s[x+len]==s[y+len])++len;
        return len;
    }
    void calc_h(){
        for(int i=1;i<=l;i++)
            h[i]=rk[i]==1?0:move(i,sa[rk[i]-1],max(h[i-1]-1,0));
    }
    int st[N][16];//h[sa[i]]~h[sa[i+2^j]] 中的最小值
    void make_st(){
        for(int i=1;i<=l;i++)st[i][0]=h[sa[i]],printf("st[%d,0]:%d\n",i,st[i][0]);
        for(int j=1;(1<<j)<=l;j++){
            int step=1<<(j-1);
            for(int i=1;i+step<=l;i++){
                st[i][j]=min(st[i][j-1],st[i+step][j-1]);
                printf("st[%d,%d]:%d\n",i,j,st[i][j]);
            }
        }
    }
    int lcp(int x,int y){// 返回长度
        if(x==y)return l-x+1;
        x=rk[x],y=rk[y];
        if(x>y)swap(x,y);
        x++;// 取不到 x
        int step=log(y-x+1)/log(2);
        return min(st[x][step],st[y-(1<<step)+1][step]);
    }
};
SA sa;
int main(){
    scanf("%s",sa.s+1);
    sa.make();
    sa.calc_h();
    sa.make_st();
    for(int i=1;i<=sa.l;i++){
        for(int j=1;j<=sa.l;j++){
            if(i!=j&&sa.lcp(i,j))printf("%d %d %d\n",i,j,sa.lcp(i,j));
        }
    }
    return 0;
}
/*
 * BUG#1: bin[i-1] 写成 bin[i+1]
 * 求后缀 (i,j)(rk[i]<rk[j]) 的 LCP,就是求 j in (rk[i],rk[j]] 的 height[j] 的最小值,即 RMQ.
 */

  转载请注明: Sshwy's Blog 后缀数组

 上一篇
[NOI2011] 道路修建 [NOI2011] 道路修建
这道题要卡空间 128M。。。 于是本来可以 DFS 的栈空间就爆了。。。 法一:玄学底层 +DFS 传参优化。。。 法二:直接拓扑。 我们从叶结点开始拓扑,处理完之后删点,然后将新一轮的叶结点拓扑,逐渐逼近根结点,直到队列为空。 因为是
2018.10.01
下一篇 
字典树 |TRIE 字典树 |TRIE
字典树 |TRIE简介字典树,其实就是一颗树。但是这颗树就像字典一样,能迅速匹配字典中的字符串。 基本性质: 根结点不包含字符,除根结点外每一个结点都只包含一个字符。 从根结点到某一结点,路径上经过的字符连接起来,为该结点对应的字符串。
2018.10.01
  目录