[UOJ#35] [UOJ后缀数组模板题] 后缀排序 [后缀数组模板]

时间：2023-03-09 08:54:20
[UOJ#35] [UOJ后缀数组模板题] 后缀排序 [后缀数组模板]

后缀数组，解决字符串问题的有利工具，本题代码为倍增SA算法

具体解释详见2009年国家集训队论文

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <cmath>

 #include <ctime>

 using namespace std;

 int    str[];

 int    Barrel[][],U[],Tmp[],SA[],H[];

 char    r[];

 void    Calc_H(const int & n,const int * Rank)

 {

     int    i,j,k=;

     for(i=;i<n;H[Rank[i++]]=k)

         for(k?k--:,j=SA[Rank[i]-];str[i+k]==str[j+k];++k);

     return ;

 }

 bool    cmp(const int * s,const int a,const int b,const int l)

 {

     return s[a]==s[b] && s[a+l]==s[b+l];

 }

 int*    Get_SA(const int & n,int  m)

 {

     int    i,j,p,*x=Barrel[],*y=Barrel[];

     memset(U,,sizeof(U));

     for(i=;i<n;++i)U[x[i]=str[i]]++;

     for(i=;i<m;++i)U[i]+=U[i-];

     for(i=n-;i>=;--i)SA[--U[x[i]]]=i;

     for(j=,p=;p<n;j<<=,m=p)

     {

         for(p=,i=n-j;i<n;++i)y[p++]=i;

         for(i=;i<n;++i)if(SA[i]>=j)y[p++]=SA[i]-j;

         for(i=;i<n;++i)Tmp[i]=x[y[i]];

         for(i=;i<m;++i)U[i]=;

         for(i=;i<n;++i)U[Tmp[i]]++;

         for(i=;i<m;++i)U[i]+=U[i-];

         for(i=n-;i>=;--i)SA[--U[Tmp[i]]]=y[i];

         for(swap(x,y),p=,x[SA[]]=,i=;i<n;++i)

         x[SA[i]]=cmp(y,SA[i-],SA[i],j)?p-:p++;

     }

     Calc_H(n,x);

     return x;

 }

 int main()

 {

     int    i,n;

     scanf("%s",r);

     n=strlen(r);

     for(i=;i<n;++i)str[i]=r[i];

     Get_SA(n+,);

     for(i=;i<=n;++i)printf("%d ",SA[i]+);

     printf("\n");

     for(i=;i<=n;++i)printf("%d ",H[i]);

     return ;

 }

在计算H数组的时候因为在计算SA数组的程序中x所代表的数组中就是Rank数组，所以不需要重新计算

相关文章