2倍倍增算法的主要思路是：用倍增的方法对每个字符开始的长度为2^k的字符串进行排序，求出排名，即rank值。

#include
    
     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
     
      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
     
    

参考：后缀数组 （）

      罗穗骞 《后缀数组——处理字符串的有力工具》