//输出ht见UOJ.35 #include
    
     #include
     
      #include
      
       const int N=1e6+5;int n,tm[N],t1[N],t2[N],SA[N],rk[N],ht[N];//SA[i]=j:排名为i的后缀开头的下标为j //rk[i]=j:以下标i开头的后缀排名为j //ht[i]:排名为i的后缀与排名为i-1的后缀的LCP长度 char s[N];void Get_SA(){    int *x=t1,*y=t2,limit=80;//首先对单个字符进行排序，limit最初就为字符集大小(就是不同字符的个数)     for(int i=0;i
       
        =k) y[p++]=SA[i]-k;//剩下的有完整第二关键字的(SA[i]>=k)按顺序，即SA[i]排，第一关键字的位置自然就是SA[i]-k         //对第一关键字的排序同对单个字符排序         for(int i=0;i
        
         =n&&SA[i]+k>=n))) x[SA[i]]=p-1;            else x[SA[i]]=p++;        if(p>=n) break;//不同字符串数已有n个，再继续倍增不会变了，break     }}void Calc_Ht(){    for(int i=0;i
         
          =ht[rk[i-1]]-1 // 因为去掉开头字符 后缀一大部分是相等的。比较明显 for(int j,k=0,i=0;i