UOJ #35. 后缀排序 后缀数组 模板

时间：2023-03-10 04:46:46
UOJ #35. 后缀排序 后缀数组 模板

http://uoj.ac/problem/35

模板题，重新理了一遍关系。看注释吧。充分理解了倍增的意义，翻倍之后对上一次排序的利用是通过一种类似于队列的方式完成的。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 const int maxn=;

 const int pl=;

 int sa[maxn+pl]={};//排名第i的是从sa[i]开始的数组

 int rk[maxn+pl]={};//i的排名

 int height[maxn+pl]={};//排名第i的与排名第i-1的最长相同前缀长度

 int temp[maxn+pl]={};//暂时的排名

 int cnt[maxn+pl]={};//第i种（字典序）前缀的有多少个（的前缀和）

 int p[maxn+pl]={};//此次需要排列的sa的储存，处理了后缀长度不同的情况。

 char ch[maxn+pl]={};

 int siz;

 bool equ(int x,int y,int l){ return rk[x]==rk[y]&&rk[x+l]==rk[y+l]; }

 void SA(){

     for(int i=;i<=siz;i++){rk[i]=ch[i];sa[i]=i;}

     for(int i,sig=,l=,pos=;pos<siz;sig=pos){

         pos=;

         for(i=siz-l+;i<=siz;i++)p[++pos]=i;//根据上一次的sa决定p的储存顺序，没有排序则排在最前。

         for(i=;i<=siz;i++) if(sa[i]>l) p[++pos]=sa[i]-l;//sa的计算是向字符串前端（左侧）拓展的

         for(i=;i<=sig;i++) cnt[i]=;

         for(i=;i<=siz;i++) cnt[rk[p[i]]]++;

         for(i=;i<=sig;i++) cnt[i]+=cnt[i-];

         for(i=siz;i>;i--) sa[cnt[rk[p[i]]]--]=p[i];//方便记忆板子的提示，只有这里是倒着扫的。

         pos=;

         for(i=;i<=siz;i++){

             if(equ(sa[i],sa[i-],l))temp[sa[i]]=pos;

             else temp[sa[i]]=++pos;

         }

         for(int i=;i<=siz;i++)rk[i]=temp[i];

         if(!l)l=;

         else l<<=;

     }int j=;

     for(int i=;i<=siz;i++){

         if(rk[i]==){j=;continue;}

         if(j)j--;

         while(ch[i+j]==ch[sa[rk[i]-]+j]){

             j++;

         }height[rk[i]]=j;

     }

 }

 int main(){

     //freopen("a.in","r",stdin);

     scanf("%s",ch+);siz=strlen(ch+);

     SA();

     for(int i=;i<=siz;i++)printf("%d ",sa[i]);

     cout<<endl;

     for(int i=;i<=siz;i++)printf("%d ",height[i]);

     return ;

 }

相关文章