后缀数组的倍增算法（Prefix Doubling）

文本内容除特殊注明外,均在知识共享署名-非商业性使用-相同方式共享 3.0协议下提供,附加条款亦可能应用。

最近在自学习BWT算法（Burrows-Wheeler transform），其中涉及到对字符串循环移位求编码。直观的办法就是模拟，使用O(n3)的时间求出BWT编码。经过简单的简化后也要O(n2logn)的时间，显然当字符串长度很大时这种方法的效率很低。 由于循环移位的结果类似后缀（二者有所不同，所以在字符串结尾添加了一个字典序严格小于所有字符的符号，例如'\0'，使得循环移位的有效部分等同于后缀），因此可以使用后缀树或后缀数组的方式优化BWT的过程。

关于学习倍增算法，你应该：

1. 理解朴素的后缀数组生成方法
2. 理解基数排序（本文使用了基数排序，至于原始的倍增算法是否是使用基数排序本人也不清楚）
3. 了解KMP算法的原理

先来谈谈KMP算法。它之所以能有效减少比对次数是因为它利用了之前比对的结果——利用前缀的自相似性跳过必然失败的匹配，直接进行有可能成功的尝试。 而倍增算法同样拥有类似的思想，例如cake拥有后缀

cake
ake
ke
e

当我们比较了每个后缀第一个字母后（2nd 1st 4th 3rd），实际上我们也知道了每个后缀的第二个字母的比较结果（1st 4th 3rd -）。类似的，后续结果也就知道了。因此，我们可以得到逐步扩展每个后缀的前缀比较结果（2 1 4 3）->（21 14 43 3-）->（214 143 43- 3--）……参考图1（本例和图中所示不同，但思路是一样的） 上述延伸过程是线性增加的。若是再贪心一点，则可以利用上一回的比较结果将该回的前缀比较长度增加一倍，即指数级增长。这也就是倍增算法的核心思路。

图1引用自NOCOW

再来谈谈利用基数排序的算法实现。基数排序分为LSD（Least significant digital）和MSD（Most significant digital）两大类。乍一看后缀数组的比较是从高位开始的（p.s. 为什么不从低位开始呢？删除一个整数而不改变相对大小关系很简单，但添加一个整数而不改变相对大小关系比较麻烦），很适合MSD。但MSD的时间开销随序列复杂度和长度增长很快，仅适用于短序列，所以LSD是个无奈之选。可以说，倍增算法的代码之所以晦涩很大一部分原因就是使用LSD的缘故。

code in C++

#include<stdio.h>
#include<string.h>
#define rank r_sa
const int MAXN=21;
char str[MAXN];
int sa[MAXN];//suffix array
int l_sa[MAXN];//low of sa
int r_sa[MAXN];//reverse mapping of sa, also known as rank array
int t_r_sa[MAXN];//temperary copy of r_sa
char BWT[MAXN];
int c[MAXN+128];//数组长度必须大于字符串长度和字符总数的最大值
bool sa_cmp(int *r,int sa1,int sa2,int j){
        //此处完美地进行了越界判断
        return (r[sa1]==r[sa2] && r[sa1+j]==r[sa2+j]);
}
int prefixdouble(char *s,int l){
        int i,j,k,m;
        
        //对后缀的第一位进行基数排序
        memset(c,0,sizeof(c));
        for(i=0;i<l;i++)
                c[ s[i] ]++;
        for(m=1;m<MAXN+128;m++)
                c[m]+=c[m-1];
        for(i=l-1;i>=0;i--)
                sa[ --c[s[i]] ]=i;

        //r_sa[i]=k 即第i个后缀排名第k
        for(i=0;i<l;i++)
                r_sa[i]=s[i];//此时仅需反映相对大小顺序

        int p;
        for(j=1;j<=l;j*=2){
                
                //由于采用LSD，先对低位进行排序
                p=0;
                //l_sa[k]=i 即排名第k的是第i个后缀
                for(i=l-j;i<l;i++)
                    l_sa[p++]=i;//长度小于j的后缀无低位关键字，直接排在最前
                for(k=0;k<l;k++)
                    if(sa[k]>=j) l_sa[p++]=sa[k]-j;//第i-j个后缀的低位关键字等于第i个后缀的高位关键字，并且高位关键字在之前已有序

                //再对高位进行排序
                memset(c,0,sizeof(c));
                for(k=0;k<l;k++)
                        c[ r_sa[ l_sa[k] ] ]++;
                for(m=1;m<MAXN+128;m++)
                        c[m]+=c[m-1];
                for(k=l-1;k>=0;k--)
                        sa[ --c[ r_sa[ l_sa[k] ] ] ]=l_sa[k];

                //更新r_sa
                memcpy(t_r_sa,r_sa,4*MAXN);
                r_sa[ sa[0] ]=p=0;
                //相邻后缀如果前缀相同，那么其rank也相同
                for(k=1;k<l;k++)
                        r_sa[sa[k]]=sa_cmp(t_r_sa,sa[k-1],sa[k],j)?p:++p;
                if(p==l-1) break;
        }
/*test
        for(k=0;k<l;k++)
                printf("%2d:%s\n",k,s+sa[k]);

        BWT[0]=s[l-2];
        for(i=1;i<l;i++)
                BWT[i]=s[sa[i]-1];
        BWT[l]='\0';
        printf("trans:");
        for(i=0;i<l;i++)
                printf("%c",BWT[i]);
*/
}
int main(){
        printf("The string inputed should short than 20 symbols.\n");
        scanf("%s",str);
        int l=strlen(str);
        prefixdouble(str,l+1);
        for(int i=0;i<l;i++)
               printf("%d ",sa[i]);
        return 0;
}