研究了一个星期的后缀数组，过程很痛苦，但还是有很多收获，付出更收获真的成正比的。发现后缀数组的强大功能，需慢慢领会。
后缀数组可以代替后缀树巧妙的解决大多数字符串问题，其强大功能主要有三个数组:
1.suff[i]，存放字符串S生成的后缀数组中排在第i位置，也就是将的n个后缀从小到大排序后把排好序的后缀的开头位置顺次放入到suff中。
2.rank[i]，rank数组跟suff[i]相对应，suff[i]是排第i的在哪，rank[i]表示第i个开始的字串排第几，即rank[suff[i]]=i
3.height[i],height加强了后缀数组的威力，height[i]表示排名第i的后缀与排名第i-1的后缀的最长公共前缀。
LCP(最长公共前缀)，LCP(i,j)表示后缀数组中第i个和第第j个后缀的最长公共前缀的长度，LCP定理：
LCP[i,j]=min{Height[k]|i+1=<k<=j};可以用RMQ来求区间内的最小值。
用2倍增算法可以在O(nlogn)时间内求出suff,rank数组。这个看了很长时间，具体实现：
suff,rank的实现：
void CreatSuff(int m)
{
int i,h,p;
//用计数排序求出长度为1的suff值
for(i=0;i<m;i++)
C[i]=0;
for(i=0;i<len;i++)
C[x[i]=r[i]]++;
for(i=1;i<m;i++)
C[i]+=C[i-1];
for(i=len-1;i>=0;i--)
suff[--C[x[i]]]=i; // 其中x存放rank的值，以上是计数排序模块
//根据suff求出rank，再利用长度为h的rank为关键字,基数排序,求出长度为2*h的suff.
for(h=1,p=0;p<len;h<<=1,m=p)
{
for(p=0,i=len-h;i<len;i++)
y[p++]=i; //y存放第二关键字排序的结果,这里有点技巧，你用上次的suff对第二关键子排序
for(i=0;i<len;i++)
if(suff[i]>=h)
y[p++]=suff[i]-h;
for(i=0;i<len;i++) //对第一关键字进行计数排序
wv[i]=x[y[i]];
for(i=0;i<m;i++)
C[i]=0;
for(i=0;i<len;i++)
C[wv[i]]++;
for(i=1;i<m;i++)
C[i]+=C[i-1];
for(i=len-1;i>=0;i--)
suff[--C[wv[i]]]=y[i];
t=x;x=y;y=t;p=1; //利用suff求rank，变量p其实是不同字符串的个数，这里让
m=p，当p=len时就结束
for(x[suff[0]]=0,i=1;i<len;i++)
x[suff[i]]=cmp(y,suff[i],suff[i-1],h) ? p-1 : p++;
}
}
int cmp(int *v,int a,int b,int h)
{
return v[a]==v[b]&&v[a+h]==v[b+h] ; //这里要满足从a和b开始长度为h的前缀相同以及从a+h和b+h开始长度为h的前缀相同，
这样才能判定长度为2h的前缀相同
}
Height的实现：求Height时要用到一个定理，令H[i]=Heigth[rank[i]],也就是以第i个开始的后缀与在后缀数组中排在他前一位后缀的公共前缀长度
利用这个定理H[i]>=H[i-1]-1可以在O(n)内求出Height，用归纳法很容易证明。
void CalHeight()
{
int k,i,p;
for(k=0,p=0;p<len;p++)
{
if(x[p]==0)
Height[x[p]]=0; //规定Height[0]=0
else
{
for(i=suff[x[p]-1];r[i+k]==r[p+k];k++); //i为在后缀数组中排在p的前一位,从两个串第k个开始比较，因为前k-1个已相等
Height[x[p]]=k;
if(k>0)
k--;
}
}
}
后缀数组的应用十分灵活,继续学习中！