桶排序、基数排序与后缀排序
Sweetlemon
2019-06-25 11:25:41
最近学后缀数组,需要接触到这些排序方法,于是乎开帖记录。
### 术语说明
本文中,“排名”可以粗浅地理解为“不大于$x$的元素个数称为$x$的排名”。但是,有重复元素的时候,假设小于$x$的元素个数是$a$,不大于$x$的元素个数是$b$,那么这些重复元素的排名各不相同,且都位于区间$(a,b]$中。
如,数组$1,1,2,3,3,4$中各元素的排名可以是$1,2,3,4,5,6$,当然也可能是$2,1,3,5,4,6$等等。
本文中要大量使用“元素数组”、“排名数组”这样的词汇,请牢记它们的含义:叫做什么数组,里面存的就是什么值。
- “元素数组”指根据排名查元素编号的数组,即$\mathrm{ele}:\left\{\mathrm{rank}\right\}\rightarrow \left\{\mathrm{id}\right\}$
- “排名数组”指根据元素编号查排名的数组,即$\mathrm{rk}:\left\{\mathrm{id}\right\}\rightarrow \left\{\mathrm{ele}\right\}$
这两个数组之间是逆映射的关系。
在桶排序中,还会用到桶数组。桶数组是根据元素值查“这个值的元素有多少个”的数组,做前缀和后就是根据元素值查“不大于这个值的元素有多少个”的数组。通常,我们使用它的后一种含义。
- “桶数组”是根据元素值查“不大于这个值的元素有多少个”的数组,即$\mathrm{bucket}:\left\{\mathrm{value}\right\}\rightarrow \left\{\mathrm{rank}\right\}$
熟悉这些映射关系,对于快速写出代码有很大帮助。
文中还用了 Pascal 的数组区间符号。`a[1...3]={1,2,3}`表示`a[1]=1,a[2]=2,a[3]=3`。
### 离散化
首先我们通过复习离散化方法,熟悉“元素数组”和“排名数组”的意义。
```cpp
int a[MAXN]; //原始数据
int ele[MAXN],rk[MAXN]; //定义见上文
bool cmp(const int lhs,const int rhs);
for (int i=1;i<=n;i++)
ele[i]=i; //初始化,假设第i名的元素下标是i
sort(ele+1,ele+1+n,cmp); //排序后,第i名元素的下标是ele[i]
//利用rk和ele的互逆关系求rk
for (int i=1;i<=n;i++)
rk[ele[i]]=i; //第i名元素的下标所对应的排名是i
bool cmp(const int lhs,const int rhs){
//利用元素给下标排序
return a[lhs]<a[rhs];
}
```
上述代码执行后,`rk`数组中的值就是离散化目标值。
### 桶排序
#### 单关键字桶排序
桶排序?这个谁不会啊?
```cpp
int a[MAXN],bucket[MAXM]; //原始数据, 桶(桶的定义域是原始数据的值域)
for (int i=0;i<MAXM;i++)
bucket[i]=0;
for (int i=1;i<=n;i++)
bucket[a[i]]++;
int pos=0;
for (int i=0;i<MAXM;i++)
for (int j=0;j<bucket[i];j++)
a[++pos]=i;
```
但是如何用桶排序求出元素数组和排名数组呢?这里介绍一种简单的办法。
我们知道,原始的桶数组记录的是“值为$x$的元素的个数”。如果对桶数组做前缀和,记录的就是“值不大于$x$的元素个数”——不就是“值为$x$的元素的(最大)排名”吗?之所以是“最大”,是因为可能有重复元素(参见“术语说明”)。于是,我们可以用这种方法得到元素数组和排名数组。
下面这段代码对于理解多关键字桶排序比较重要,请认真阅读。如果对代码不太理解,请接着阅读下面的说明。
```cpp
int a[MAXN],bucket[MAXN],ele[MAXN],rk[MAXN];
for (int i=0;i<MAXM;i++)
bucket[i]=0;
for (int i=1;i<=n;i++)
bucket[a[i]]++;
for (int i=1;i<MAXM;i++)
bucket[i]+=bucket[i-1]; //求前缀和
// 此时bucket数组的意义就是“给值,求最大排名”
// 下面用bucket数组求ele数组
for (int i=n;i;i--){ // 这个循环是倒序的
int trank=bucket[a[i]]; // 求出i号元素的排名
bucket[a[i]]--; // 排名trank已经被i占用了,下一个来的元素要用上一个可用的排名
ele[trank]=i; // 排名为trank的元素编号是i
// 上面这三条语句通常缩写为
// ele[ bucket[a[i]]-- ]=i;
}
//此时, a[ele[1]],a[ele[2]],...,a[ele[n]]就是有序的了
//再利用rk和ele的互逆关系求rk
for (int i=1;i<=n;i++)
rk[ele[i]]=i; //第i名元素的下标所对应的排名是i
```
现在问题来了,为什么这个循环是倒序的呢?也就是说,我们需要搞清楚,排名的“分配原则”是什么。同时我们还要搞懂这行关键代码:`ele[ bucket[a[i]]-- ]=i;`
首先,如果数组中没有重复元素,那么`bucket[a[i]]`只会被访问一次,其中的值正是`i`号元素的真正排名。
但如果数组中有重复元素呢?举个例子,如果`a[1...6]={1,4,3,1,3,2}`,那么在求前缀和之前,`bucket[1...4]={2,1,2,1}`;求前缀和之后,`bucket[1...4]={2,3,5,6}`。那么,$1$的“最大排名”是$2$,$3$的“最大排名”是$5$。
我们倒序循环分配排名。首先`i=6`,`ele[ bucket[a[6]]-- ]=6`。执行语句时`bucket[a[6]]=bucket[2]=3`,于是我们得到了$6$号元素的排名是$3$,也就是被赋予了排名$3$的元素是$6$号(`ele[3]=6`)。根据`--`运算符的规则,我们把`bucket[2]`的值减$1$,那么执行后`bucket[2]=2`。这表示,排名$3$已经被占用了,下一个值为$2$的元素只能使用排名$2$——当然,由于数列中只有一个元素的值是$2$,因此不存在所谓的“下一个元素”。
接着`i=5`,`ele[ bucket[a[5]]-- ]=5`。`bucket[a[5]]=bucket[3]=5`,那么这次我们把排名$5$赋给`a[5]`。这时`bucket[3]--`,表示下一个值为$3$的元素只能使用排名$4$——在这里就表示,靠前的一个$3$将使用排名$4$。
继续模拟这个过程,最后`ele[1...6]={1,4,6,3,5,2}`。在模拟的过程中我们发现,**值相同的元素,先者总是得到较大的排名**。就有些像孔融让梨,孔融是把大的梨让出去,先拿到排名的元素是把靠前的排名让给后拿到排名的元素。
而我们倒序循环,原本靠后的元素将先得到排名,结果就是值相同的元素,原本靠后的,排名也较大(即在排序后的数组里也靠后)。这正满足了“稳定性”的定义——这样它就是“稳定排序”了。
当然,这么做的意义远不止如此,正是这一操作,为桶排序提供了可扩展性。请看——
#### 多关键字桶排序
什么叫“多关键字”呢?就有点像中考成绩排序——先按总分等级排序,总分等级相同的再按A+数排序,A+数相同的……概括地说,就是,优先按第一关键字排序,如果第一关键字相同,再按第二关键字排序。
下面我们只讨论两个关键字的情形;在此基础上,很容易扩展出更多关键字的排序。
还记得上面讲的“稳定性”吗?我们有一个思路——**先按第二关键字排序,再按第一关键字做稳定排序**。
为什么先排次要关键字呢?可以这么理解——第一次排序的结果会被第二次排序打乱,因此是次要的。第一次排序只是为了第二次排序在**关键字相同**时,提供原先的相对位置。也就是,第一次排序的功效,体现在了排序前相对位置上。
那么我们就可以写出多关键字桶排序的代码了。
```cpp
int a[MAXN],b[MAXN];// a 为主要关键字, b为次要关键字
// ele_b是第一次排序时用的ele数组
int bucket[MAXN],ele[MAXN],ele_b[MAXN],rk[MAXN];
for (int i=0;i<MAXM;i++)
bucket[i]=0;
for (int i=1;i<=n;i++)
bucket[b[i]]++;
for (int i=1;i<MAXM;i++)
bucket[i]+=bucket[i-1];
for (int i=n;i;i--)// 仍然注意这个循环是倒序的
ele_b[ bucket[b[i]]-- ]=i;
//现在b[ele_b[1]],b[ele_b[2]],...,b[ele_b[n]]是有序的
//我们下一次桶排序循环的时候,就按照ele_b[n],ele_b[n-1],...,ele_b[1]的顺序
for (int i=0;i<MAXM;i++)
bucket[i]=0;
for (int i=1;i<=n;i++)
bucket[a[i]]++;
for (int i=1;i<MAXM;i++)
bucket[i]+=bucket[i-1];//这三个for循环基本相同
for (int i=n;i;i--)// 按我们上面说的做!
ele[ bucket[ a[ ele_b[i] ] ]-- ]=ele_b[i];
```
整段代码最难理解的应该就是`ele[bucket[a[ele_b[i]]]--]=ele_b[i];`这一行了。足足四层嵌套,让不少多关键字桶排序和基数排序的初学者望而生畏。下面我们解析它。
对`b`做排序的时候,我们已经写过一次三层嵌套了。`ele_b[ bucket[b[i]]-- ]=i;`,意思是`bucket[b[i]]`中存着`b[i]`的排名,那么排名为`bucket[b[i]]`的元素编号就是`i`。
对`a`做排序的时候,我们不是要按`ele_b[n],ele_b[n-1],...,ele_b[1]`的顺序做嘛——于是,运用换元法,把`ele_b[i]`带入原来的`i`中,不就得到了这一行代码吗?
于是,双关键字的桶排序就写好了。这也就是[这道题](https://www.luogu.org/problemnew/show/T84081)的解法。
### 基数排序
基数排序其实就是多关键字的桶排序。比如,给三位数排序,第一关键字是百位,第二关键字是十位,第三关键字是个位。
但实际操作中,我们所用的模数不是$10$,而是$2$的幂。根据[挑战](https://www.luogu.org/problemnew/show/P4604)这道题的经验,我们取$256(2^8)$为模,把$32$位整数(也就是`int`)分为四个关键字进行排序,分别排序四次就好了。
```cpp
#define MASK 255
int a[MAXN],b[MAXN]; //a储存原数据, b在排序过程中会发生改变
int b1[BUSKN],b2[BUSKN],b3[BUSKN],b4[BUSKN]; //val -> rank, 四次排序的桶
int e1[MAXN],e2[MAXN],e3[MAXN],e4[MAXN]; //rank -> ID, 四次排序的ele数组
for (int i=1;i<=n;i++){
int t=b[i]=a[i];
b1[t&MASK]++,t>>=8;
b2[t&MASK]++,t>>=8;
b3[t&MASK]++,t>>=8;
b4[t&MASK]++; //分别加到桶里
}
for (int i=1;i<=MASK;i++)
b1[i]+=b1[i-1],b2[i]+=b2[i-1],
b3[i]+=b3[i-1],b4[i]+=b4[i-1]; //给桶做前缀和
//核心步骤——赋予排名
for (int i=n;i;i--)
e1[b1[b[i]&MASK]--]=i, b[i]>>=8;
for (int i=n;i;i--)
e2[b2[b[e1[i]]&MASK]--]=e1[i],b[e1[i]]>>=8;
for (int i=n;i;i--)
e3[b3[b[e2[i]]&MASK]--]=e2[i],b[e2[i]]>>=8;
for (int i=n;i;i--)
e4[b4[b[e3[i]]&MASK]--]=e3[i];
for (int i=1;i<=n;i++)
ayano(a[e4[i]],' '); //按顺序输出整数
```
### 后缀排序
给后缀排序是建立后缀数组(Suffix Array)的关键操作。
字符串`s[1...n]`的后缀就是指这些子串:`s[1...n],s[2...n],s[3...n],...,s[n...n]`。按照后缀的起始点,分别把它们编号为$1,2,3,\cdots,n$。
“后缀排序”就是对这$n$个后缀(就是$n$个字符串)进行排序。当然不是真的排序,只是求出元素数组和排名数组罢了。
在这里重新强调元素数组和排名数组的定义:
- 元素数组,此处称作后缀数组或`sa`数组,表示排名为`i`的后缀的编号是`sa[i]`
- 排名数组,此处称作`rank`(缩写为`rk`)数组,表示编号为`i`的后缀排名为`rk[i]`
还是那句话,“名副其实”,后缀数组里的东西是后缀(的编号),排名数组里的东西是排名。
如何给后缀排序呢?最简单的方法当然是直接应用一遍快速排序,时间复杂度是$\mathrm{O}(n\log n)$,足够快了吧。
可惜的是,这个时间复杂度是错的。由于比较两个字符串是$\mathrm{O}(n)$而非$\mathrm{O}(1)$的,快速排序需要$\mathrm{O}(n\log n)$次比较,因此正确的复杂度应该是$\mathrm{O}(n^2 \log n)$,无法承受。
那么改成基数排序吧?字符串的排序是按照字典序,也就是以第一个字符为第一关键字、以第二个字符为第二关键字,以此类推。可是这样会有$n$个关键字,需要(桶)排序$n$次,每次排序的时间复杂度是$\mathrm{O}(n)$,合起来达到$\mathrm{O}(n^2)$,依然无法承受。
做不出来的时候怎么办?看看我们是不是漏条件了啊。
上面的两种方法可是不仅可以用于后缀排序,还可以用于“给$n$个字符串排序”啊。这不就相当于,“后缀”的条件完全没有利用上吗?那怎么可能做得出来啊。
“后缀”的条件是,这些字符串有很多的公共部分!利用这些公共部分,就能改善我们算法的时间复杂度!
利用这个条件的方法很多,像后缀树、后缀平衡树、后缀自动机等。当然,我们在这里要介绍的是最简单的一种——倍增法求后缀数组。
倍增法的主要思想是,“用排名代替具体的元素”。
我们用字符串`"aabaaaab"`做例子(这个例子好经典,为什么?因为它是 IOI 2009 国家集训队论文里边的啊~),它的后缀有`"b","ab","aab","aaab","aaaab",'baaaab","abaaaab","aabaaaab"`。
首先,我们把所有的后缀调整成一样长的,也就是(假装)我们在字符串后面补了一些空字符(`'\0'`,字典序是最小的;下面用`0`表示)。那么后缀就变成了`"b0000000","ab000000","aab00000","aaab0000","aaaab000",'baaaab00","abaaaab0","aabaaaab"`。补这些字符并不影响字典序,因为我们规定,比不出大小时短的字符串较小。
思考这个问题:某些元素,按$(a,b)$双关键字排序的排名是$x$,按$(c,d)$双关键字排序的排名是$y$,那么按$(a,b,c,d)$四关键字排序的排名是否就相当于按$(x,y)$双关键字排序的排名呢?(关键字的顺序表示主次顺序。)
思考后可以发现,答案是肯定的。
那么,我们就把这个字符串的所有长度为$1$的块进行排序;接着把它所有长度为$2$的块按照组成它的两个$1$块的排名(在前面的是主要关键字,在后面的是次要关键字)进行双关键字排序,就可以得到$2$块的排名;然后再把$4$块按照$2$块的排名进行双关键字排序,得到$4$块的排名……直到块的长度不小于$n$为止。此时每一个块都是原串的后缀(因为长度不小于$n$,因此除了`s[1...n]`,其余块都一定要越过`s[n]`补零,也就成了后缀),我们就得到了后缀的排序。
引用一下集训队论文里的图片——
![后缀排序基本过程](https://cdn.luogu.com.cn/upload/pic/61393.png)
从图中我们可以看到,每一次排序都是把上次排序的**rank数组作为元素值**,也就是“用排名代替具体的元素”。排序的主要关键字是上一次的`rank[i]`,次要关键字是上一次的`rank[i+w]`,其中$w=2^k$。
从图中我们还可以看到,我们不必实际地去补“0”,只需要在所找的$2$块、$4$块等超出边界的时候直接令他们的原排名为$0$即可。
那么,我们就可以实现代码了。
首先是桶排序部分的代码。我们已经把次要关键字`rk[i+w]`的**元素数组**制作好并存到了数组`tp`里,因此相当于次要关键字已经排好序了。注意,`sa`和`tp`都是元素数组。
```cpp
void bucket_sort(int n,int m){
// 任务: 根据主要关键字的值数组rk和次要关键字的排名数组tp, 计算元素数组sa
// n是字符串长, m是rk和tp的值域([1,m])
// 各映射的信息: rk: id->val, tp: rank->id, bucket: val->rank, sa: rank->id
for (int i=0;i<=m;i++)
bucket[i]=0;
for (int i=1;i<=n;i++)
bucket[rk[i]]++;
for (int i=1;i<=m;i++)
bucket[i]+=bucket[i-1];
for (int i=n;i;i--)
sa[ bucket[ rk[ tp[i] ] ]-- ] = tp[i];
}
```
四重嵌套那一行可能比较难写。一个较为快速的推法是,把映射关系写下来,再根据映射关系写(“量纲分析”)。
1. 要求出`sa`,先写`sa[ ]=`
2. `sa`的值是`id`,值是`id`的只有`tp`,写下`sa[ ]=tp[i]`
3. `sa`的定义域是`rank`,值域是`rank`的只有`bucket`,写下`sa[bucket[ ]--]=tp[i]`(是`bucket`,所以伴随着`--`)
4. `bucket`的定义域是`val`,值域是`val`的只有`rk`,写下`sa[bucket[rk[ ]]--]=tp[i]`
5. `rk`的定义域是`id`,值域是`id`的已知量只有`tp`,写下`sa[bucket[rk[tp[i]]]--]=tp[i]`。
接着再来实现后缀排序的主函数。
```cpp
void suffix_sort(int n){
//字符串长度为n
//先做一遍长度为1的块的排序
//因为是第一遍排序, 所以第一关键字是字符大小
//第二关键字随意指定一个,那么第二关键字的元素数组可以设为1,2,...,n
int m='z'-'/'; //假设字符集是0-9,A-Z,a-z
//m表示字符集大小,也就是值数组的值域
for (int i=1;i<=n;i++)
//分别求出第一遍排序的主要关键字 值数组 和次要关键字 元素数组
rk[i]=str[i]-'/', tp[i]=i;
bucket_sort(n,m);
//下面开始重复排序,也就是倍增过程
for (int w=1,p=0;w<n && p<n;w<<=1,m=p){
//w表示上一次排序的块长
//为进行排序,先制作tp数组
p=0; //记录排名
//先处理那些次要关键字已经超过了串的末尾,也就是达到补零位置的块
for (int i=n-w+1;i<=n;i++)
tp[++p]=i; //将“++p”这个排名分配给i这个块
//这些块的次要关键字都一样,任意指定一些最靠前的排名就好了
//接着根据上一回排序的“排名”的元素数组,制作本次的元素数组
for (int i=1;i<=n;i++)
//取上一回第i名的块,分配排名
if (sa[i]>w) //如果某个块的编号小于w,那么这次就不会作为后继块(sa[i]-w已经小于0了)
tp[++p]=sa[i]-w; //给sa[i]-w(前驱块的编号)分配++p的排名
//上述循环顺序进行, 先遍历到的块比较小, 分配靠前的排名
//现在tp数组制作完成,开始进行排序
bucket_sort(n,m);
//现在根据sa数组制作rk数组
swap(rk,tp); //tp数组已经使用完毕了(排序后就不需要上一次排序的信息了),下面我们用它来储存上一轮的rk数组
rk[sa[1]]=1; //排名为1的元素所对应的排名是1
p=1; //此处p的含义是已经分配了的排名
for (int i=2;i<=n;i++)
if (tp[sa[i]]==tp[sa[i-1]] && tp[sa[i]+w]==tp[sa[i-1]+w])
//上述两个条件说明, 组成 sa[i]和sa[i-1],即排名为i和i-1的两个元素的两个块完全相同
rk[sa[i]]=p;
else
rk[sa[i]]=++p;
//到此处,p表示已经分配出的排名种类数;同时也是值数组的值域,因此可以作为下一轮的m值
//p=n表示已经区分出了n种后缀,后缀排序就完成了
}
}
```
通过这两个函数,我们就计算出了`sa`和`rk`数组,也就实现了后缀排序。输出`sa`数组就可以通过[这道模板题](https://www.luogu.org/problemnew/show/P3809)了。
可能这里的注释还有一些不清楚的地方,但是暂时无法进一步完善了(哭)。如果有什么问题在评论区提吧。
那么这篇文章就结束了。
2020 年 6 月 15 日 Update:
### 后缀 LCP——height 数组
后缀数组通常的搭档是 height 数组。首先弄清楚它的定义:`height[i]` 表示**排名**为 $i$ 的后缀(`SA[i]` 号后缀)与**排名**为 $i-1$ 的后缀(`SA[i-1]` 号后缀)的最长公共前缀(LCP)的长度。
该如何求 height 数组呢?有一个很简单的做法,求出原字符串的哈希,接下来就可以 $\mathrm{O}(\log n)$ 地通过二分求出 `height[i]` 的值,从而可以 $\mathrm{O}(n\log n)$ 地求出 height 数组了。
上面这个方法虽然思想很简单,但是实现起来稍显复杂,而且复杂度也不是最优。下面介绍一种更简单快捷的求 height 数组的方法。
首先需要知道一个定理:$\mathrm{height}[\mathrm{rank}[i]]\ge \mathrm{height}[\mathrm{rank}[i-1]]-1$,用文字叙述就是,**第 $i$ 号**后缀所对应的排名的 height 不小于**第 $i-1$ 号**后缀所对应的排名的 height;也就是说,第 $i$ 号后缀(记为 $\mathtt{B}$)与排名比 $\mathtt{B}$ 小 $1$ 的后缀的 LCP 长度,不小于第 $i-1$ 号后缀(记为 $\mathtt{xB}$,注意它恰好比第 $i$ 号后缀多一个字符)与排名比 $\mathtt{xB}$ 小 $1$ 的后缀的 LCP 长度减 $1$。
如何简要说明这个定理呢?实际上,我们只需要证明 $\mathrm{height}[\mathrm{rank}[i-1]]\ge 2$ 的情况(小于等于 $1$ 的情况是平凡的)。
由于“排名比 $\mathtt{xB}$ 小 $1$ 的后缀”(即 $\mathrm{SA}[\mathrm{rank}[i-1]-1]$ 号后缀)与 $\mathtt{xB}$ 的 LCP 长度不小于 $2$,因此可以把它设为 $\mathtt{xA}$,并且我们还知道 $\mathtt{A}$ 与 $\mathtt{B}$ 的 LCP 长度等于 $\mathtt{xA}$ 与 $\mathtt{xB}$ 的 LCP 长度减 $1$,即 $\mathrm{height}[\mathrm{rank}[i-1]]-1$。
现在我们知道存在一个与 $\mathtt{B}$ 的 LCP 长度为 $\mathrm{height}[\mathrm{rank}[i-1]]-1$ 的后缀 $\mathtt{A}$,当然 $\mathtt{A}$ 和 $\mathtt{B}$ 排名不一定相邻,但 $\mathtt{A}$ 一定排在 $\mathtt{B}$ 前面。这里可以感性理解一下,既然离得相对较远的两个后缀都有这么长的 LCP,那么 $\mathrm{height}[\mathrm{rank}[i]]$ 肯定不会小于这个数(严格的证明和下面的一个性质有关,当然那个性质我也不会给出严格证明);于是这个方法就证明完毕了。
由于上面这个定理是按照后缀编号顺序给出的,因此我们在求 height 的时候也要按后缀编号顺序递推。
```cpp
void get_height(int n){
int last_height=0;
for (int i=1;i<=n;i++){
//i 表示后缀编号
(last_height>0)?(last_height--):(0); //根据引理
if (rk[i]==1){
height[1]=0;
continue;
}
while (tstr[i+last_height]==tstr[sa[rk[i]-1]+last_height])
last_height++;
height[rk[i]]=last_height;
}
}
```
height 数组可以用来快速求出任意两个后缀的 LCP。有定理如下:**排名**为 $i$ 的后缀与**排名**为 $j$ 的后缀(设 $i<j$)的 LCP 长度等于 $\min(\mathrm{height}[i+1],\mathrm{height}[i+2],\cdots,\mathrm{height}[j])$。
这个定理也比较好理解。设 $\min(\mathrm{height}[i+1],\mathrm{height}[i+2],\cdots,\mathrm{height}[j])=k$,那么**排名**为 $i$ 的后缀与**排名**为 $i+1$ 的后缀、**排名**为 $i+1$ 的后缀与**排名**为 $i+2$ 的后缀、**排名**为 $j-1$ 的后缀与**排名**为 $j$ 的后缀,等等,它们的 LCP 长度都至少是 $k$,由传递性知这个 $k$ 长 LCP 一直都是一样的。而由于后缀都是排序好的,因此一旦有一个地方出现变化,后续是不可能再变回来的,因此 $k+1$ 位的字符一定是不一样的。综上,定理就得证了。
这个过程也可以用“后缀树”来理解。这和树上求 LCA 有些许相似之处。
因此,height 数组就把许多字符串问题转化为了区间问题,可以用 ST 表、双指针等方法解决。
有些多串的问题,可以用分隔符把它们连接成一个串,用后缀数组求解。但是要特别注意,分隔符要用不同的,比如 $\mathtt{abc|def/ghi@jkl}$ 等,否则分隔符可能会干扰 height 数组!
### 代码
下面附上一份~~叠氮化钠~~ 后缀数组(SA)的参考代码,便于~~复习~~ 背诵。目前[这份代码](https://loj.ac/submission/837602)在 LOJ 上荣膺第三快。
代码中使用了很多临时变量,以“减少不连续内存访问”。
```cpp
void suffix_sort(int n){
int m='z'-'0'+1;
for (int i=1;i<=n;i++)
rk[i]=tstr[i]-'0'+1,tp[i]=i;
tp[n+1]=0; //这行代码是做什么的呢?下面会解释
bucket_sort(n,m);
for (int p=0,w=1;p<n;m=p,w<<=1){
p=0;
for (int i=n-w+1;i<=n;i++)
tp[++p]=i;
for (int i=1;i<=n;i++){
int sai=sa[i]; //卡常数
(sai>w)?(tp[++p]=sai-w):(0);
}
bucket_sort(n,m);
swap(rk,tp);
rk[sa[1]]=1;
p=1;
for (int i=2;i<=n;i++){
int sai=sa[i],saim1=sa[i-1]; //卡常数
rk[sai]=(tp[sai]==tp[saim1] && tp[sai+w]==tp[saim1+w])?
(p):(++p);
}
}
}
void bucket_sort(int n,int m){
//tp: 2nd rk->id, sa: 1st rk->id
//rk: 1st id->val, bucket: 1st val->rk
for (int i=0;i<=m;i++)
bucket[i]=0;
for (int i=1;i<=n;i++)
bucket[rk[i]]++;
for (int i=1;i<=m;i++)
bucket[i]+=bucket[i-1];
for (int i=n;i;i--){
int tpi=tp[i]; //卡常数
sa[bucket[rk[tpi]]--]=tpi;
}
}
void get_height(int n){
int lh=0;
for (int i=1;i<=n;i++){
(lh>0)?(lh--):(0);
int rki=rk[i];
if (rki==1){
height[1]=0;
continue;
}
int j=sa[rki-1];
while (tstr[i+lh]==tstr[j+lh])
lh++;
height[rki]=lh; //记得这里不要写错
}
}
```
2020 年 7 月 27 日 Update:
没错,我又回来了,这次我只加了一行代码,就是在第一次桶排序前将 $\mathrm{tp}[n+1]$ 清空为 $0$。
为什么要这么做呢?
看这行代码,`rk[sai]=(tp[sai]==tp[saim1] && tp[sai+w]==tp[saim1+w])?(p):(++p);`。这是计算 $\mathrm{rk}$ 时用的,但是 $\mathrm{sa}[i]+w$ 这里真的不会数组越界吗?
很遗憾,确实会越界;但幸运的是,至多访问到 $\mathrm{tp}[n+1]$ 而不会访问到之后的数组。
这是为什么呢?
由于逻辑运算符的短路特性,只有 $\mathrm{tp}[\mathrm{sa}[i]]$ 与 $\mathrm{tp}[\mathrm{sa}[i-1]]$ 相等时,才会进行后面的比较并访问 $\mathrm{tp}[\mathrm{sa}[i]+w]$ 和 $\mathrm{tp}[\mathrm{sa}[i-1]+w]$ 。我们只要说明这时 $\forall u\in \{i-1,i\},\mathrm{sa}[u]+w\le n+1$,即 $w\le n-\mathrm{sa}[u]+1$ 即可。
$w\le n-\mathrm{sa}[u]+1$ 是什么意思呢?$w$ 是上一次排序完成的后缀(块)长度,$n-\mathrm{sa}[u]+1$ 是 $\mathrm{sa}[u]$ 号后缀的长度。
我们用反证法。假设 $w> n-\mathrm{sa}[u]+1$,那说明上次排序完成后,$\mathrm{sa}[u]$ 号后缀的全部字符(连同后面的空字符)都已经被纳入排序范围。在这种情况下,我们要说明,是不可能出现 $\mathrm{tp}[\mathrm{sa}[i]]$ 与 $\mathrm{tp}[\mathrm{sa}[i-1]]$ 相等的情况的。因为此时的 $\mathrm{tp}$ 表示上一轮排序时的排名,因此也就是说,$\mathrm{sa}[u]$ 号后缀在上一轮排序完成后不会和另一个后缀拥有相同的排名。
如果“另一个后缀”在上一轮排序中已经被完全考虑,那由于任意两个后缀的大小都是可比的(一定不会出现两个相等的后缀),因此它们的排名不相等。如果“另一个后缀”在上一轮排序中未被完全考虑,那么因为 $\mathrm{sa}[u]$ 号后缀的最后有一个空字符,所以 $\mathrm{sa}[u]$ 号后缀一定小于“另一个后缀”,排名也不相等。
综上,若 $w> n-\mathrm{sa}[u]+1$ 就一定不会出现 $\mathrm{tp}[\mathrm{sa}[i]]=\mathrm{tp}[\mathrm{sa}[i-1]]$ 的情况,因此这个语句最多访问到 $\mathrm{tp}[n+1]$。
至于为什么要清空 $\mathrm{tp}[n+1]$,当然是为了养成良好习惯,以免多组数据的时候爆零两行泪嘛。