字尾數組是我見過的這麼多算法中，最晦澀難懂的一個之一。
他本是隻是幾個數組，嚴格意義上來說不能算是一個資料結構，隻是他求出來的sa[]數組和height[]在字元串統計中非常的有用。其具體的用法就先不在這裡說，本文隻是介紹求解的方法，并給出模闆。
首先，得介紹字尾數組是什麼個東西。所謂字尾數組，顧名思義就是對于一個字元串，我求出他所有的字尾的一個排名，記錄到sa[]數組中，sa[1]就表示字典序最小的字尾的首字元開始位置。然後對應的我們可以求出Rank[]排名數組，和height[]。
其次，再說說求字尾數組的方法，這裡我說的是倍增算法(da)，時間複雜度為O(NlogN)。當然了還有更快的dc3算法，複雜度為O(N)但是程式設計複雜度和了解難度更高。但是這兩個算法的精髓就在于對基數排序的yun'yong下面就說說倍增算法用到的幾個數組。
sa[]：下标表示字尾的排名，裡面存儲字尾的首字母位置
y[]：長度為2k的子串，按照第二個關鍵字
x[]：長度為2k的子串，按照第一個關鍵字
c[]：基數排序用的統計數組
然後我們就可以開始說說，如何去求這個sa[]數組了。既然說到了基數排序，我們第一步肯定就是用它對第一個字母先進行初步的排序。可能你覺得這個基數排序很奇怪，但這正是它的巧妙之處。如果不懂得話，多在紙上自己走幾次就了解了。
for(i=0;i<n;i++) c[x[i]]++; //首先統計每個字元出現的次數
for(i=1;i<m;i++) c[i]+=c[i-1]; //然後累加字首和
for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i; //最後從後往前确定排第幾的是哪一個字元串 你會發現，經過第一次基數排序之後，出來的順序并不是一個嚴格的順序。因為它隻按照第一個字母排序，如果出現相等的情況，就會自動按照長度長的在前面。是以說，我們得繼續按照第二個關鍵字排序。
如果按照一個一個關鍵字的排序，那麼顯然時間上會退化到O(N^2)不可接受，是以說我們要充分利用前面排序的資訊。這裡比較晦澀難懂，我上圖來解釋。
第一關鍵字已經排完了，顯然不能浪費，于是我們把它後移一下，在他前面加一個字母，于是就得到了右邊的子串列。當然，有些子串已經滿了不能再加，便去掉不管。可以看到，原本的第一關鍵字變成了第二關鍵字（空的地方補空）。這麼操作之後，原本排好序的第一關鍵字變成了第二關鍵字，這個子串列相當于按照第二關鍵字排序了。這個具體操作也比較簡單，之前的sa數組減去k即可。
如此之後，我們就有了兩個關鍵字的排序順序，接下來要做的就是首先按照第一關鍵字重排，然後第一關鍵字相同就按照第二關鍵字排序。如此一來，我們就以長度為2k的關鍵字排完了序，之後再循環倍增這個k，重複之前的，直到全關鍵字覆寫。再上幾個圖加深了解：
經過這樣一系列的倍增操作，我們就可以比較快速的求出字尾數組sa[]。代碼如下：
for(int k=1,tot=0;tot<n;k<<=1,m=tot)
{
memset(c,0,sizeof(c));
for(i=0;i<n;i++) c[x[i]]++;
for(i=1;i<m;i++) c[i]+=c[i-1]; //基數排序先統計字元出現次數以及字首和
for(i=n-k,tot=0;i<n;i++) y[tot++]=i; //那些長度不夠的字尾就直接按照之前的排序放到y中
for(i=0;i<n;i++) if (sa[i]>=k) y[tot++]=sa[i]-k; //把第一關鍵字前面添加長度為k的字首，得到隻按照第二關鍵字排序的子串列
for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i]; //基數排序，兩個關鍵字的順序合并成一個，第一關鍵字相等再比較第二個
for(i=tot=1,t=x,x=y,y=t,x[sa[0]]=0;i<n;i++) //對所有子串重新标号，如果用目前關鍵字能區分大小的，就用不同編号
x[sa[i]]=cmp(y,sa[i-1],sa[i],k)?tot-1:tot++; //如果不能區分的，就用相同的編号，下一個關鍵字的時候繼續比較
} 最後，我們就是要求height數組了。所謂height數組，height[i]就是指在所有字尾中，排名第i的字尾與排名第i-1的字尾的lcp的長度。所謂lcp就是指兩個字元串的最長公共字首，至于這個有什麼用，還是一樣，這裡不談，隻談如何求。
還是一樣，如果暴力的求時間複雜度可以到O(N^2)。但是我們可以利用一個非常好的性質，我們設height[Rank[i]]=h[i]，那麼這個h[]，有性質h[i]>=h[i-1]-1。具體證明如下：
設 suffix(k)是排在suffix(i-1)前一名的字尾，則它們的最長公共字首是h[i-1]。
當h[i-1]>1時，我們不妨設suffix(k) 為”abcee…”suffix(i-1)為 “abdee…”，前後對照可知它們的最長公共字首長度為2，那我們現在來考慮suffix(i)=”bdee”，那麼排在它前面的是哪一個呢，其實我們不得而知，但是我們知道一個下界，suffix(k+1)=”bcee”
假如suffix(k+1)剛好排在suffix(i)的前一個，那麼他們的最長公共字首=1，此時h[i]=h[i-1]-1。如果suffix(k+1)不排在suffix(i)的前一個，而是前幾個，可知在suffix(k+1)和suffix(i)之間插進了一個suffix(l)，可想而知suffix(l)既要比suffix(k+1)大，又要比suffix(i)小，那麼它的第一個字元一定是’b’，第二個字元一定在’c’和’d’之間，後面的不用考慮可知suffix(l)與suffix(i)的最長公共字首>=suffix(k+1)與suffix(i)的最長公共字首，既h[i]≥h[i-1]-1恒成立。
當h[i-1]<=1時，h[i-1]-1<=0，由h[]數組的定義可知，h[i]>=0，是以h[i]≥h[i-1]-1恒成立。
有了這個性質，我們就可以從小到大，使得這個h數組裡面的數值依次遞增，可以優化到O(N)的複雜度。代碼如下：
for(i=1;i<n;i++) Rank[sa[i]]=i;
for(i=0;i<n-1;h[Rank[i++]]=k)
for(k?k--:0,j=sa[Rank[i]-1];s[i+k]==s[j+k];k++) 字尾數組本身就介紹完畢了，接下來說說模闆應用題，給出整合的模闆。這裡我的模闆是要在字元串最後加上一個空字元，然後Rank數組從1開始計算。先給出題目 SPOJ DISUBSTR 。
大緻題意是，給你一個字元串，問你這個字元串總共有多少個不同的子串。
我們可以這麼考慮，每個子串一定是某一個字尾的字首，那麼問題就變成了，求所有字尾中有多少個不同的字首。我們按照字典序也即sa[]的順序來計算。顯然，每考慮一個新的字尾，都會産生n-sa[i]個新的字首，但是這麼多字首中，又有h[i]個與之前的重複。因為h[i]即為lcp，對應這麼多個相同的字首。是以最後的答案就是 Σ(n-sa[i]-h[i])。
#include<bits/stdc++.h>
#define LL long long
#define N 100010
using namespace std;
struct Suffix_Array
{
int sa[N],Rank[N],h[N],n;
int xx[N],yy[N],c[N]; char *s;
bool cmp(int *s,int x,int y,int k)
{return (s[x]==s[y])&&(s[x+k]==s[y+k]);}
void ins(char *str) {s=str;n=strlen(s)+1;}
void SA()
{
memset(c,0,sizeof(c));
int *x=xx,*y=yy,m=130,*t,i;
for(i=0;i<n;i++) x[i]=s[i];
for(i=0;i<n;i++) c[x[i]]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
for(int k=1,tot=0;tot<n;k<<=1,m=tot)
{
memset(c,0,sizeof(c));
for(i=0;i<n;i++) c[x[i]]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-k,tot=0;i<n;i++) y[tot++]=i;
for(i=0;i<n;i++) if (sa[i]>=k) y[tot++]=sa[i]-k;
for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
for(i=tot=1,t=x,x=y,y=t,x[sa[0]]=0;i<n;i++)
x[sa[i]]=cmp(y,sa[i-1],sa[i],k)?tot-1:tot++;
}
}
void cal_height()
{
int i,j,k=0;
for(i=1;i<n;i++) Rank[sa[i]]=i;
for(i=0;i<n-1;h[Rank[i++]]=k)
for(k?k--:0,j=sa[Rank[i]-1];s[i+k]==s[j+k];k++);
}
} SA;
char s[N];
int main()
{
int T_T;
cin>>T_T;
while(T_T--)
{
scanf("%s",s);
int n=strlen(s);
SA.ins(s);SA.SA();
SA.cal_height();
LL ans=0;
for(int i=1;i<=n;i++)
ans+=n-SA.h[i]-SA.sa[i];
printf("%lld\n",ans);
}
}