注意x,y数组的意义

x[i]表示编号为i的后缀的第一关键字

y[i]表示第二关键字排名为i的后缀编号

h[i]表示编号为i的后缀与其前一名的最大公共前缀

height[i]表示排名为i的后缀与其前一名的最大公共前缀

h[i]>=h[i-1]-1

 

代码打的比较丑，有时间重新打一遍

1 #include
     
       2 using namespace std; 3 const int N=2000010; 4 int n,s[N]; 5 int m,x[N],y[N],sa[N],cnt[N],rank[N]; 6 int h[N],height[N]; 7 char ss[N]; 8 void build_sa(){ 9     for(int i=0;i
      
       =n-k;i--) y[num++]=i;16         for(int i=0;i
       
        =k) y[num++]=sa[i]-k;17         for(int i=0;i
        
         =n) break;30         m=num;31     }32     for(int i=0;i
         
          ='0'&&ss[i]<='9') s[i]=ss[i]-'0';53         else if(ss[i]>='A'&&ss[i]<='Z') s[i]=ss[i]-'A'+10;54         else s[i]=ss[i]-'a'+36;55         x[i]=s[i];56     }57     m=62;58     build_sa();build_height();59     for(int i=0;i