今天看了一下洛谷sx视频，后缀数组双关键字排序瞬间秒懂，昨天刚了一下午没有看懂的后缀数组基数排序代码有了一点点突破。
对第二关键字桶排序，保持相对顺序不变，则个位数字有序，对第一关键字桶排序，由于第一关键字相同情况下个位总是递增或持平，所以保持有序。
——《高级数据结构》
#include<cstdio>
#include<cstring>
using namespace std;
//获取后缀数组中对应后缀的原本位置
#define GetRealPos()
{
SA12[pos12]<0?SA12[pos12]*3+1:(SA12[pos12]-n0)*3+2)
}
//二元组的排序比较
inline bool cmp(int a1,int a2,int b1,int b2)
{
return (a1<b1||(a1==b1&&a2==b2));
}
//三元组的排序比较
inline bool cmp(int a1,int a2,int a3,int b1,int b2,int b3){
return (a1<b1||(a1==b1&&cmp(a2,a3,b2,b3)));
}
//基数排序（对特定位的）。参数依次为：原后缀数组指针，排序结果数组指针，对应字符数组指针，排序个数以及对字符集离散化之后的范围
void radixSort(int* oldIdx,int* newIdx,int* origin,int n,int upperBound)
{
//单次桶排序
int* cnt=new int[upperBound+1];
for (int i=0;i<=upperBound;i++)
cnt[i]=0;
for (int i=0;i<n;++i)
cnt[origin[oldIdx[i]]]++;
for(int i=0,sum=0;i<=upperBound;++i)
{
int tmp=cnt[i];cnt[i]=sum;sum+=tmp;
}
for (int i=0;i<n;++i)
newIdx[cnt[origin[oldIdx[i]]]++]=oldIdx[i];
delete [] cnt;
}
//构造后缀数组主函数，参数意义同倍增算法中主函数的参数
void suffixArray(int* st,int* SA,int n,int upperBound){
//以下3个整数分别为模3余0,1,2的后缀位置个数
int n0=(n+2)/3,n1=(n+1)/3,n2=n/3,n12=n0+n2;
//被采样的后缀（即位置模3不为0的那些后缀）
int* s12=new int[n12+3];
s12[n12]=s12[n12+1]=s12[n12+2]=0;
//被采样的后缀的后缀数组
int* SA12=new int[n12+3];
SA12[n12]=SA12[n12+1]=SA12[n12+2]=0;
//未被采样的后缀的后缀数组（即位置模3为0的那些后缀）
int* s0=new int[n0];
int* SA0=new int[n0];
//初始化采样后缀
for (int i=0,j=0;i<n+(n%3==1);++i)
if (i%3) s12[j++]=i;
//对被采样后缀按照第一个“字符”进行基数排序
radixSort(s12,SA12,st+2,n12,upperBound);
radixSort(SA12,s12,st+1,n12,upperBound);
radixSort(s12,SA12,st,n12,upperBound);
//以下为对“字符”进行离散化的过程
int cnt=0,pre0=-1,pre1=-1,pre2=-1;
for(int i=0;i<n12;++i)
{
if (st[SA12[I]]!=pre0||st[SA12[i]+1]!=pre1||st[SA12[i]+2]!=pre2){
cnt++;pre0=st[SA12[i]];pre1=st[SA12[i]+1];pre2=st[SA12[i]+2];
}
if(SA12[i]%3==1)
s12[SA12[i]/3]=cnt;
else s12[SA12[i]/3+n0]=cnt;
}
//如果存在相同字符，那么需要递归构造后缀数组
if (cnt<n12){
suffixArray(s12,SA12,n12,cnt);//递归处理
for (int i=0;i<n12;i++)
s12[SA12[i]]=i+1;
}
else //否则，由于任意两个字符都不相同，可以直接得到后缀数组
for (int i=0;i<n12;++i)
SA12[s12[i]-1]=i;
//构造未被采样后缀的后缀数组
for (int i=0,j=0;i<n12;++i)
if (SA12[i]<n0) s0[j++]=3*SA12[i];
radixSort(s0,SA0,st,n0,upperBound);
//以下过程将两次构造的后缀数组合并为最终结果
for (int pos0=0,pos12=n0-n1,k=0;k<n;++k){
int i=GetRealPos();
int j=SA0[pos0];
//i为被采样后缀集合中当前最小后缀，j为未被采样后缀集合中当前最小后缀
bool is12First;
if (SA12[pos12]<n0){
is12First=cmp(st[i],s12[SA12[pos12]+n0],st[j],s12[j/3]);
else if12First=cmp(st[i],st[i+1],s12[SA12[pos12]-n0+1],st[j],st[j+1],s12[j/3+n0]);
//根据上文中的比较规则对这两者进行比较，取较小的优先加入后缀数组
if (is12First)
{
SA[k]=i;
pos12++;
if (pos12==n12)
for (k++;pos0<n0;pos0++,k++)
SA[k]=SA0[pos0];
}
else {
SA[k]=j;
pos0++;
if (pos0==n0)
for (k++;pos12<n12;pos12++,k++)
SA[k]=GetRealPos();
}
}
//释放内存
delete [] s12;delete [] SA12;delete [] SA0;delete [] s0;
}
}
DC算法
DC3算法是DC算法的特殊情况。DC算法的后缀采样方式是选取呢些后缀位置模3不为0的后缀，因此，我们通过将该采样过程一般化，从而得到DC（Difference Cover modulov）算法。也就是说，DC3是v=3的情形。接下来，我们将和DC3算法一样一步一步进行构建，读者可以对两个算法进行对比。
步骤一：采样
定义集合D属于[0，v)，D满足{（i-j）mod v|i,j属于D}=[0,v)。
类似DC3的定义，有Bk={i|i属于[0，n]且i mod v=k}，其中k属于[0,v)。那么，采样集合C现在为：C=Uk属于DBk.
步骤二:构建后缀采样集合的后缀数组
对于Rk，现在我们没v个字符一组形成新的“字符”：Rk=[tktk+1…tk+v-1] [tk+tk+v+1…tk+2v-1]…直到T的末尾。
同样，定义R为所有Rk首尾相接的结果。利用基数排序和递归，我们同样可以得到被采样后缀的后缀数组，类似DC3。
步骤三 计算未被采样的后缀数组名次
令D=[0,v)-D,则同样被采样集合为C=Uk属于DBk。对某个k属于D，我们单独对后缀集合Suffix(Bk)进行排序。这一步与DC3中有一些小的区别：我们需要找到一个l，使得（k+l）mod v属于D。这样做是为了找到L元组来表示从位置i开始的后缀（ti,ti+1,…ti+l-1,Rank(Suffix(i+l))）,可见，如果Rank(Suffix(i+l))已知，等价于(i+l) mod v属于D，同时注意i mod v=k，因此l需要满足(k+l) mod v属于D。
现在需要证明的是上述l一定存在。根据定义，对k属于[0,v)，存在i，j属于D，使得(i-j)同余于k（mod v），令l为j，则有（k+l）同余于i（mod v），得证。这里对于每个k，使对应的l可以首先预处理出来。
由于存在有D个未被采样的后缀集合，故上述算法需要执行D次。
步骤四：合并若干个名次数组
现在面对的问题不是二路归并了，而是多路归并。如果用DC3同样的比较方式进行合并的话，至少需要O(nvlog2v)的时间复杂度，所以需要换一个思路。
首先，将被采样后缀分成D个有序集合，即对k属于D，将后缀集合Suffix(Bk)分离出来变成有序的。因为已经处理出了Suffix©,所以上述过程可以在线性时间复杂度内完成。至此，我们得到了v个有序后缀集合。接下来进一步将后缀根据其第一个“字符”（即v元组，见步骤二）进行分类。也就是说，首先根据k的值将后缀分成k个集合，接下来根据第一个“字符”进一步对每个集合细分，同时，每个集合内部又是有序的。假设Suffix(Bk,a)为集合Suffix(Bk)中首“字符”为a的后缀集合，那么我们通过细分，得到的结果类似于：
Suffix(B0,a),Suffix(B1,a)…Suffix(Bv-1,a),Suffix(B0,b)…
不难发现，上述过程同样可以在线性时间复杂度内完成。这样做的好处在以下合并过程中就体现出来了——对于每个“”字符”a,我们合并集合Suffix(B0,a),Suffix(B1,a)…,Suffix(Bv-1,a)成为一个有序集合。如果这一步完成，那么接下来只需要根据首“字符”进一步合并，即得到所需要的后缀数组了。假设当前合并首“字符”为a的那些集合，对于两个待比较的后缀Suffix(i)和Suffix（j），我们找到这样的l，使得(i+l) mod v属于D且(j+l) mod v属于D,有了步骤三的证明，这样的l一定可以找到。所以Rank(i+l)和Rank(j+l)是可比较的。进一步，由于Suffix(i)和Suffix(j)具有相同的首字母a，所以它们的序关系就等价于Rank(i+l)与Rank(j+l)的序关系。至此，有了比较函数之后就可以对集合进行合并了。
类似于DC3算法的时间复杂度证明，这里递归式的规模也是衰减的。由于v的存在，最后的时间复杂度实际上为O(nv）.
该算法的意义在于，通过恰当的实现方式，可以将除了输入，输出空间以外的额外空间复杂度降到O（nv的1/2）。参考论文研究。介绍DC算法的目的是为了能够较全面的看待DC3算法并了解它是DC算法的特殊情况，通过两者相互比较对DC3算法有较好的认识。
京公网安备 11010502036488号