Lflame

后缀数组 --- 自己的模板 (封装版)

int cnt[100005] , tmp[100005] , fir[100005] , sec[100005] ;

int my_log[100005] ;


struct Suffix_Array

{

char s[100005] ;

int len , up , SA[100005] , rk[100005] , minn[100005][20] , height[100005];

void get_SA(){

for(int i=0;i<=up;++i)cnt[i]=0 ;

for(int i=1;i<=len;++i)cnt[fir[i]]++ ;

for(int i=1;i<=up;++i)cnt[i]+=cnt[i-1] ;

for(int i=len;i>=1;--i)SA[cnt[fir[i]]--]=i ;

int k=1;

while(k<len){

int zj=0 ;

for(int i=len-k+1;i<=len;++i)sec[++zj]=i ;

for(int i=1;i<=len;++i) if(SA[i]-k>=1)sec[++zj]=SA[i]-k ;

for(int i=1;i<=up;++i)cnt[i]=0 ;

for(int i=1;i<=len;++i)cnt[fir[sec[i]]] ++ ;

for(int i=1;i<=up;++i)cnt[i]+=cnt[i-1] ;

for(int i=len;i>=1;--i)SA[cnt[fir[sec[i]]]--]=sec[i] ;

swap(fir,tmp) ;

zj=0 ; fir[SA[1]]=++zj ;

for(int i=2;i<=len;++i){

if(SA[i]+k<=len && SA[i-1]+k<=len && tmp[SA[i]]==tmp[SA[i-1]] && tmp[SA[i]+k]==tmp[SA[i-1]+k])

fir[SA[i]]=zj ;

else fir[SA[i]]=++zj ;

}

up=zj ;

k<<=1 ;

}

}


void get_height(){

int zj=0 ;

for(int i=1;i<=len;++i)rk[SA[i]]=i ;

for(int i=1;i<=len;++i){

if(rk[i]==1){ SA[rk[i]]=0 ; continue ; }

int t=SA[rk[i]-1] ;

while(s[t+zj]==s[i+zj])zj ++ ;

height[rk[i]]=zj ;

zj=max(0,zj-1) ;

}

}


void pre_do(){

for(int i=1;i<=len;++i)minn[i][0]=height[i] ;

for(int k=1;(1<<k)<=len;++k){

for(int i=1;i<=len;++i){

if(i+(1<<(k-1))>len)minn[i][k]=minn[i][k-1] ;

else minn[i][k]=min(minn[i][k-1],minn[i+(1<<(k-1))][k-1]) ;

}

}

}


inline int query(const int &l,const int &r){

int t=my_log[r-l+1] ;

return min(minn[l][t],minn[r-(1<<t)+1][t]) ;

}


inline int lcp(const int &p1,const int &p2){

if(p1<=0 || p2<=0 || p1>=len || p2>=len)return 0;

if(p1==p2)return len-p1+1 ;

int l=rk[p1] , r=rk[p2] ;

if(l>r)swap(l,r) ;

return query(l+1,r) ;

}


void init(){

len=(int)strlen(s+1) , up=0;

memset(SA,0,sizeof(SA)) , memset(height,0,sizeof(height)) , memset(rk,0,sizeof(rk));

for(int i=1;i<=len;++i){ fir[i]=(int)s[i] , up=max(up,fir[i]) ; }

get_SA() ;

get_height() ;

pre_do() ;

}

};


评论(1)

热度(2)