字尾數組（倍增法）

字尾數組（Suffix Array）：将某個字元串的所有字尾按字典序排序後得到的數組。

算法：樸素實作：直接将所有字尾進行排序，将n個長度為O(n)的字元串進行排序，時間複雜度O(n^2*logn)；倍增算法：通過充分利用各個字尾之間的聯系，将構造字尾數組的最壞時間複雜度成功降至O(n*logn)。

倍增法實作：首先計算從每個位置開始的長度為1的子串的順序，再利用這個結果計算長度為2的子串的順序，接下來計算長度為4的子串的順序，不斷倍增，直到長度大于等于n就得到了字尾數組。

下面，我們用sa[i]表示按字典序排序後第i小子串的開始位置；用S[sa[i],k]表示從位置sa[i]開始的長度為k的字元串子串，其中，剩餘字元不足k個時，表示的是從sa[i]開始到字元串末尾的子串；rank[sa[i]]為S[sa[i],k]在所有排好序的長度為k的子串中是第幾小的（核心：rank[sa[i]]=i，其中i代表第幾小）。

最後，從每個位置開始的排序部分，因為比較rank[sa[i]]和rank[sa[j]]就相當于比較S[sa[i],k]和S[sa[j],k]，比較rank[sa[i]+k]和rank[sa[j]+k]就相當于比較S[i+k,k]和S[j+k,k]（或S[i,2*k]和S[j,2*k]）。是以，我們可以利用上一步的rank來高效地比較長度為2*k的子串，并将它們排序。

代碼：

int n,k;
int rank[max_n+1];
int tmp[max_n+1];

//比較（rank[i],rank[i+k]）和（rank[j],rank[j+k]）
bool cmp_sa(int i,int j)
{
        if(rank[i]!=rank[j])   return rank[i]<rank[j];
        else{
                 int ri=i+k<=n?rank[i+k]:-1;
                 int rj=j+k<=n?rank[j+k]:-1;
                 return ri<rj;
        }
}

//計算字元串S的字尾數組
void creat_sa(string S,int *sa)
{
        n=S.length();

        //初始長度為1，rank直接取字元的編碼
       for(int i=0;i<=n;i++)
       {
               sa[i]=i;
               rank[i]=i<n?S[i]:-1;
       }

       //利用對長度為k的排序的結果對長度為2*k的排序
       for(k=1;k<=n;k*=2)
       {
              sort(sa,sa+n+1,cmp_sa);
         
              //先在tmp中臨時儲存新計算的rank，再轉存回rank中
              tmp[sa[i]]=0;
              for(int i=1;i<=n;i++)
                       tmp[sa[i]]=tmp[sa[i-1]]+(cmp_sa(sa[i-1],sa[i])?1:0);
              for(int i=0;i<=n;i++)
                        rank[i]=tmp[i];
        }
}