桶排序、基数排序与后缀排序

最近学后缀数组，需要接触到这些排序方法，于是乎开帖记录。

术语说明

本文中，“排名”可以粗浅地理解为“不大于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。

离散化

首先我们通过复习离散化方法，熟悉“元素数组”和“排名数组”的意义。

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数组中的值就是离散化目标值。

桶排序

单关键字桶排序

桶排序？这个谁不会啊？

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的元素的（最大）排名”吗？之所以是“最大”，是因为可能有重复元素（参见“术语说明”）。于是，我们可以用这种方法得到元素数组和排名数组。

下面这段代码对于理解多关键字桶排序比较重要，请认真阅读。如果对代码不太理解，请接着阅读下面的说明。

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+数相同的……概括地说，就是，优先按第一关键字排序，如果第一关键字相同，再按第二关键字排序。

下面我们只讨论两个关键字的情形；在此基础上，很容易扩展出更多关键字的排序。

还记得上面讲的“稳定性”吗？我们有一个思路——先按第二关键字排序，再按第一关键字做稳定排序。

为什么先排次要关键字呢？可以这么理解——第一次排序的结果会被第二次排序打乱，因此是次要的。第一次排序只是为了第二次排序在关键字相同时，提供原先的相对位置。也就是，第一次排序的功效，体现在了排序前相对位置上。

那么我们就可以写出多关键字桶排序的代码了。

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中，不就得到了这一行代码吗？

于是，双关键字的桶排序就写好了。这也就是这道题的解法。

基数排序

基数排序其实就是多关键字的桶排序。比如，给三位数排序，第一关键字是百位，第二关键字是十位，第三关键字是个位。

但实际操作中，我们所用的模数不是10，而是2的幂。根据挑战这道题的经验，我们取256(2^8)为模，把32位整数（也就是int）分为四个关键字进行排序，分别排序四次就好了。

#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]补零，也就成了后缀），我们就得到了后缀的排序。

引用一下集训队论文里的图片——

从图中我们可以看到，每一次排序都是把上次排序的rank数组作为元素值，也就是“用排名代替具体的元素”。排序的主要关键字是上一次的rank[i]，次要关键字是上一次的rank[i+w]，其中w=2^k。

从图中我们还可以看到，我们不必实际地去补“0”，只需要在所找的2块、4块等超出边界的时候直接令他们的原排名为0即可。

那么，我们就可以实现代码了。

首先是桶排序部分的代码。我们已经把次要关键字rk[i+w]的元素数组制作好并存到了数组tp里，因此相当于次要关键字已经排好序了。注意，sa和tp都是元素数组。

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]。

接着再来实现后缀排序的主函数。

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数组就可以通过这道模板题了。

可能这里的注释还有一些不清楚的地方，但是暂时无法进一步完善了（哭）。如果有什么问题在评论区提吧。

那么这篇文章就结束了。

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 的时候也要按后缀编号顺序递推。

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）的参考代码，便于复习 背诵。目前这份代码在 LOJ 上荣膺第三快。

代码中使用了很多临时变量，以“减少不连续内存访问”。

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> 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]$，当然是为了养成良好习惯，以免多组数据的时候爆零两行泪嘛。