2倍倍增算法的主要思路是：用倍增的方法对每个字符开始的长度为2^k的字符串进行排序，求出排名，即rank值。
#include<iostream>
using namespace std;
const int maxlen = 10011;
int tsa[maxlen], RANK[maxlen], sum[maxlen], sa[maxlen], TRANK[maxlen];
void radix_sort(int j, int len){
//对第二关键字计数排序，tsa代替sa为排名为i的后缀是tsa[i]
memset(sum,0,sizeof(sum));
for (int i=1; i<=len; i++){
if(i+j>len) RANK[i+j]=0;
sum[ RANK[i+j] ]++;
}
for (int i=1; i<=maxlen; i++) sum[i]+=sum[i-1];
for (int i=len; i>0; i--)
tsa[ sum[ RANK[i+j] ]-- ]=i;
//对第一关键字计数排序,构造互逆关系
memset(sum,0,sizeof(sum));
for (int i=1; i<=len; i++) sum[ RANK[i] ]++;
for (int i=1; i<=maxlen; i++) sum[i]+=sum[i-1];
for (int i=len; i>0; i--)
sa[ sum[ RANK[ tsa[i] ] ]-- ]= tsa[i];
}
void calc_sa(int *s, int len){
int p;
// TRANK存放字符串
// int len=s.size();
for (int i=0; i<len; i++) TRANK[i+1]=s[i];
// 对单个字符进行计数排序
for (int i=1; i<=len; i++) sum[ TRANK[i] ]++;
for (int i=1; i<=maxlen; i++) sum[i]+=sum[i-1];
for (int i=len; i>0; i--)
sa[ sum[ TRANK[i] ]-- ]=i;
// 计算RANK
RANK[ sa[1] ]=1;
for (int i=2,p=1; i<=len; i++){
if (TRANK[ sa[i] ]!=TRANK[ sa[i-1] ]) p++;
RANK[ sa[i] ]=p;
}//第一次的sa与RANK构造完成
for (int j=1; j<=len; j*=2){
// 对长度为j的字符串进行排名
radix_sort(j,len);
TRANK[ sa[1] ]=1; p=1; //用TRANK代替RANK
// 计算RANK
for (int i=2; i<=len; i++){
if(sa[i]+j > len) RANK[ sa[i]+j ]=0;
if(sa[i-1]+j > len) RANK[ sa[i-1]+j ]=0;
if ((RANK[ sa[i] ]!=RANK[ sa[i-1] ]) ||
(RANK[ sa[i]+j ]!=RANK[ sa[i-1]+j ])) p++;
TRANK[ sa[i] ]=p;//空间要开大一点，至少2倍
}
for (int i=1; i<=len; i++) RANK[i]=TRANK[i];
}
}
void calc_height(int *s, int len){
int k=0,j;
for(int i=0; i<len; height[i++]=k){
if(RANK[i]==1)continue;
for(k?k--:0; j=sa[ RANK[i]-1 ]; s[i+k]==s[j+k]; k++);
}
}
罗穗骞 《后缀数组——处理字符串的有力工具》