1 int n,m;  char s[310000]; 2 int rank[310000]; 3 int cnt[310000],cnt_rank[310000]; 4 int rank1[310000],rank2[310000]; 5 int SA[310000],tempSA[310000];//应该是桶 6 void get_suffix_rank(){ 7     memset(cnt,0,sizeof(cnt)); 8     //以下是对单个字母排序 9     for(int i=0;i<n;i++)  cnt[s[i]]++;//计数10     for(int i=‘a‘;i<=‘z‘;i++)  cnt[i]+=cnt[i-1];//把计数堆起来，这样后面搞名次直接用这个堆起来的数就行了11     for(int i=0;i<n;i++)  rank[i]=cnt[s[i]]-1;//这里搞了个‘$‘，所以要-1，让‘$‘的名次为012     //因为名次是堆出来的，所以这个版本a,b,a,a对应的名次是1,4,1,1（单个字符名次）（不知道其他版本是不是一。一）13     for(int l=1;l<n;l*=2){//倍增长度14         for(int i=0;i<n;i++){//搞出rank[1]和rank[2]15             rank1[i]=rank[i];16             rank2[i]=(i+l<n) ? rank[i+l] : 0;17         }18         //基数排序排rank1和rank219         memset(cnt_rank,0,sizeof(cnt_rank));20         for(int i=0;i<n;i++)  cnt_rank[rank2[i]]++;21         for(int i=1;i<n;i++)  cnt_rank[i]+=cnt_rank[i-1];//还是堆名次22         for(int i=n-1;i>=0;i--)  tempSA[--cnt_rank[rank2[i]]]=i;//应该是进桶23         memset(cnt_rank,0,sizeof(cnt_rank));24         for(int i=0;i<n;i++)  cnt_rank[rank1[i]]++;25         for(int i=1;i<n;i++)  cnt_rank[i]+=cnt_rank[i-1];26         for(int i=n-1;i>=0;i--)  SA[--cnt_rank[rank1[tempSA[i]]]]=tempSA[i];//rank1[tempSA[i]]应该相当于出桶27         rank[SA[0]]=0;28         for(int i=1;i<n;i++){29             rank[SA[i]]=rank[SA[i-1]];30             if(rank1[SA[i]]!=rank1[SA[i-1]] || rank2[SA[i]]!=rank2[SA[i-1]])  rank[SA[i]]++;31         }32     }33 }34 int main(){freopen("ddd.in","r",stdin);35     cin>>n;36     char ch=getchar();  while(ch<‘a‘||ch>‘z‘)  ch=getchar();37     for(int i=0;i<n;i++){  s[i]=ch;  ch=getchar();}38     s[++n]=‘$‘;//这应该是个记号，让a比a$小39     get_suffix_rank();