Code analysis of suffix array template

    Today I saw the template code of suffix array , Finally understand the functions of each part of the template , But the details are not fully understood , It seems that we can only set a template for the time being , The following is the template and notes ;

   

/*
sa[i] :  Express   In the first i Suffix of position   Start subscript 

rank[i] :  The suffix  suffix(i) What's the number 

RANK Which rank do you rank    SA Indicates who is in the first place  （ Just remember this ）

height[i] :  Express  sa[i-1]  And  sa[i]  Of LCP  value , That is, the longest common prefix of two suffixes adjacent to each other 

h[i]:  be equal to Height[Rank[i]], Express  suffix(i) With the top one  LCP value 
*/
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#define maxn 20010
#define ws wss
int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
int cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
// Used to compare the first keyword with the second keyword ,
//  The special thing is , In the pretreatment ,r[n]=0( Less than the previous character )
void da(int *r,int *sa,int n,int m)// here N More than the input N More 1, A character added manually for , Used to avoid CMP Time goes beyond the border 
{
    int i,j,p,*x=wa,*y=wb,*t;
    for(i=0;i<m;i++) ws[i]=0;
    for(i=0;i<n;i++) ws[x[i]=r[i]]++;
    for(i=1;i<m;i++) ws[i]+=ws[i-1];
    for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;// The pretreatment length is 1
    // The top four lines are the length of 1 The process of sorting prefixes by cardinality 
    for(j=1,p=1;p<n;j*=2,m=p)// Through the length that has been calculated J Of SA, Come and ask for 2*J Of SA
                            //j Is the prefix length , p Is the number of suffixes of different sizes , m Is a value greater than all values 
{
    for(p=0,i=n-j;i<n;i++) y[p++]=i;//  Special treatment of... Without a second keyword 
    for(i=0;i<n;i++)
    if(sa[i]>=j)
      y[p++]=sa[i]-j;
    //  The above code makes y Save the results sorted by the second keyword  , The results sorted by the second keyword can take advantage of the previous sa Array 
     for(i=0;i<n;i++) wv[i]=x[y[i]];
     for(i=0;i<m;i++) ws[i]=0;
     for(i=0;i<n;i++) ws[wv[i]]++;
     for(i=1;i<m;i++) ws[i]+=ws[i-1];
     for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];// Sort by the first keyword , Cardinality sorting part 

        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)  // In exchange for x and y,rank Values are saved in x Array ,p For the number of different strings , Update name times           Group x[], Pay attention to judge the same 
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
    return ;
}
int rank[maxn],height[maxn];
void calheight(int *r,int *sa,int n){ //  here N Is the actual length 
    int i,j,k=0;                 // height[] The legal scope of is  1-N,  among 0 Is the character added at the end 
    for(i=1;i<=n;i++) rank[sa[i]]=i;//  according to SA seek RANK
    for(i=0;i<n;height[rank[i++]]=k)//  Definition ：h[i] = height[ rank[i] ]
    for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);// according to  h[i] >= h[i-1]-1  To optimize the calculation height The process 
    return ;
}

int main()
{
        int sa[20010];
        int n,i,j,k;
        int t1,t2;
        n=8;
        int note[9]={1,1,2,1,1,1,1,2};
        da(note,sa,n+1,4); // Note that this is n+1, Because an ending character is added to distinguish and compare 
        calheight(note,sa,n);
        for(i=1;i<=n;i++)
            cout<<sa[i]<<endl;
        cout<<".."<<endl;
        for(j=1;j<=n;j++)
            cout<<height[j]<<endl;
        return 0;
}

      The comments explain which module implements what functions , This is reflected. c++ Encapsulation of language , In fact, if the program statement is difficult to understand , The expedient is to understand which part implements which function as soon as possible , What operations can be realized by using some modules , The specific principle process is deepened in the continuous application .