n-sa[k]+1-height[k] 累加

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 const int maxn=1000+10; 6 char s[maxn]; 7 int sa[maxn],t[maxn],t2[maxn],c[maxn]; 8 int rank[maxn],height[maxn]; 9 void build_sa(int n,int m)10 {11     int i,*x=t,*y=t2;12 13     for(i=0;i
        
         =0;i--) sa[--c[x[i]]]=i;17     for(int k=1;k<=n;k<<=1)18     {19         int p=0;20         for(i=n-k;i
         
          =k) y[p++]=sa[i]-k;22 23         for(i=0;i
          
           =0;i--) sa[--c[x[y[i]]]]=y[i];27 28 swap(x,y);29 p=1;x[sa[0]]=0;30 for(i=1;i
           
            =n) break;33 m=p;34 }35 }36 void getHeight(int n)37 {38 int i,k=0;39 for(i=1;i<=n;i++) rank[sa[i]]=i;40 for(i=0;i