原理很简单，但是看代码学习实在是太慢了、
花了4个小时、
bool cmp(int *y,int a,int b,int k)
{ int aa=y[a],bb=y[b],aaaa=y[a]+k,bbbb=y[b]+k; if(aaaa>=len)aaaa=-1; if(bbbb>=len)bbbb=-1; return aa==bb&&aaaa==bbbb; } void da() { int *x=t1,*y=t2; m=26; for(i=0;i<m;i++)cc[i]=0; for(i=0;i<len;i++)cc[x[i]=str[i]-'a']++; for(i=1;i<m;i++)cc[i]+=cc[i-1]; for(i=len-1;i>=0;i--)sa[--cc[x[i]]]=i; for(k=1;k<=len;k<<=1) { p=0; for(i=len-k;i<len;i++)y[p++]=i; for(i=0;i<len;i++)if(sa[i]>=k)y[p++]=sa[i]-k; for(i=0;i<m;i++)cc[i]=0; for(i=0;i<len;i++)cc[x[y[i]]]++; for(i=1;i<m;i++)cc[i]+=cc[i-1]; for(i=len-1;i>=0;i--)sa[--cc[x[y[i]]]]=y[i]; m=1; swap(x,y);x[sa[0]]=0; for(i=1;i<len;i++) x[sa[i]]=cmp(y,sa[i],sa[i-1],k)?m-1:m++; if(m>=len)break; } } void calcheight() { for(i=0;i<len;i++)rank[sa[i]]=i; height[0]=0; int k=0; for(i=0;i<len;i++) { if(!rank[i])continue; int j=sa[rank[i]-1]; if(k)--k; while(str[i+k]==str[j+k])++k; height[rank[i]]=k; } }