后缀数组是我见过的这么多算法中，最晦涩难懂的一个之一。
他本是只是几个数组，严格意义上来说不能算是一个数据结构，只是他求出来的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);
}
}