从梓轩学姐提交记录那里搞来的，简单易懂，没有那些奇奇怪怪的东西...

#include
     
      #include
      
       const int MAXN=100000,D=50;int n,str[MAXN+D];int sa[MAXN+D],rank[MAXN+D],height[MAXN+D];int p[MAXN+D],temp[MAXN+D],cnt[MAXN+D];inline bool equ(int x,int y,int l){return rank[x]==rank[y]&&rank[x+l]==rank[y+l];}void init(){	char ch=getchar();	while(ch>='a'&&ch<='z')str[n++]=ch-'a',ch=getchar();}void doubling(){	str[n]=rank[n]=-1;	for(int i=0;i
       
        =l)p[pos++]=sa[i]-l;		memset(cnt,0,sizeof cnt);		for(i=0;i
        
         =0;i--)sa[--cnt[rank[p[i]]]]=p[i];		for(temp[sa[0]]=pos=0,i=1;i