【总结】线性时间排序与基于线性时间排序的后缀数组倍增算法

我现在所要提到的是一种简单的基数排序。
假设给一些一位数排序,要求在稳定排序的条件下,输出按照不递减序排序后序列第个元素是原序列的第几个元素。
我们维护,表示原序列中不超过的数的总数目,这只需要即可做到。
我们从后向前考虑在新序列中的排名。
如果每种数不超过1个,那么显然原序列的第个数在新序列中的排名为,这是显然的。
那么比如说有若干个相同的数呢?
由于是稳定排序,那么从后往前,原序列中第一个为的数在新序列中排名为,第二个为,以此类推,第个排名为.
那么这个问题得到了解决。只需要的复杂度。

现在考虑给位数的整数排序。(如果不足k位可认为在前面补0)
我们从后向前依次对每一位进行基数排序。
维护表示排序后序列中的排名为的数是原序列中的第几个数。
由于稳定性,初始.
假设现在正要给第位排序,那么现在可以认为序列在第位是稳定且有序的,也即:
然后我们容易利用一次的基数排序得到新的数组。
则最终的答案序列为
这个过程的时间复杂度为,事实上是时间的算法,常数与项数有关。
它的局限性在于:每一项的值域应非常小,如果每一项的值域大小为,设项数为,那么复杂度应为.

后缀数组是在字符串问题中能够有很大贡献的一种工具。具体来说,对于长度为的字符串,我们需要首先计算出,分别表示字典序第小的后缀的开头位置,以及开头位置为的后缀在所有后缀中字典序是第几小。
我们可以暴力取出所有后缀进行排序,可是比较的复杂度可能达到,这样总复杂度就达到了,显然在达到级别显然无法接受。
考虑后缀数组的倍增算法,即依次计算所有后缀仅考虑前个字符时的排名,然后计算所有后缀仅考虑前个字符时的排名,...以此类推。
显然通过所有后缀前个字符的排名情况,容易得出所有后缀前个字符的排名情况。
我们只需将两端个字符的排名合并为一个二元组,则新的排名情况可以通过对这些二元组排序得到。
如果每次进行sort,那么时间复杂度为.
然而每次对二元组进行的排序,值域级别至多为,于是我们可以进行线性时间排序,使得复杂度降低为.
这里附上带有充分注释的代码,相信一定容易理解。

int val[N], sa[N], sav[N], rank[N], newval[N], add[N];
void build_sa(int n, int m) {//n个字符,标号0~n-1;字符的值域为[0,m-1]
 int i;//sa[i]:排名第i小的后缀的开头位置;val[i]:以位置i开头的后缀此时的大小比较值;rank[i]:以位置i开头的后缀的排名
 for(i=0;i<m;++i)add[i]=0;
    for(i=0;i<n;++i)++add[val[i]=s[i]];
    for(i=1;i<m;++i)add[i]+=add[i-1];
    for(i=n-1;i>=0;--i)sa[--add[val[i]]]=i;//利用基数排序给n个后缀的第一个字符排序
 for(int k=1;k<=n;k<<=1){//此次循环将利用后缀前k个字符的排名得出前k*2个字符的排名
     int p=0;//根据后k*2个字符中后k个字符的排名由小到大依次加入
     for(i=n-k;i<n;++i)sav[p++]=i;//后面没有东西了,字典序最小,优先加入
     for(i=0;i<n;++i)if(sa[i]-k>=0)sav[p++]=sa[i]-k;//剩下的按照后k个字符的排名加入
     for(i=0;i<m;++i)add[i]=0;
        for(i=0;i<n;++i)++add[val[sav[i]]];
        for(i=1;i<m;++i)add[i]+=add[i-1];
        for(i=n-1;i>=0;--i)sa[--add[val[sav[i]]]]=sav[i];//根据前k*2个字符的前k个字符大小比较值基数排序得出后缀前k*2字符的排名
     p=1;//重新计算每个后缀前k*2个字符的大小比较值
     newval[sa[0]]=0;//新的排名为0的后缀的大小比较值定义为0
     for(i=1;i<n;++i)//排名为i的后缀与排名为i-1的后缀若前k*2个字符完全相同则大小比较值也与其完全相同,否则比他大1
         newval[sa[i]]=val[sa[i]]==val[sa[i-1]]&&val[sa[i]+k]==val[sa[i-1]+k]?p-1:p++;
        for(i=0;i<n;++i)//得到新的大小比较值
         val[i]=newval[i];
        if(p>=n)//如果已经存在至少n种大小的后缀,显然已经完成排序,退出
         break;
        m=p;//更改大小比较值的域
 }
    for(i=0;i<n;++i)//简单的映射计算rank[]
     rank[sa[i]]=i;
}
comments powered by Disqus