SA模版，然后我发现我写的SA其实有问题……
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[500005];
int n,rank[500005],rank2[500005],height[500005],sa[500005],rmq[500005][20],ws[500005],wv[500005],er[20],log2[500005];
int cmp(int *r,int a,int b,int l){return (r[a]==r[b])&(r[a+l]==r[b+l]);}
void GetSA(char *r,int *sa,int n,int m){
int i,j,p,*x=rank,*y=rank2,*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;}
for(j=p=1;p<n;j*=2,m=p){
for(p=0,i=n-j;i<n;i++)y[p++]=i;
for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
for(i=0;i<m;i++)ws[i]=0;
for(i=0;i<n;i++)ws[wv[i]=x[y[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];
for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
void CalHeight(char *r,int *sa,int n){
int i,j,k=0;
for(i=1;i<=n;i++)rank[sa[i]]=i;
for(i=0;i<n;height[rank[i++]]=k)for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}
void RMQ(){
int i,j;
er[0]=1;
for(i=1;i<20;i++)er[i]=er[i-1]<<1;
log2[0]=-1;
for(i=1;i<=n;i++)log2[i]=(i&(i-1))?log2[i-1]:log2[i-1]+1;
for(i=1;i<=n;i++)rmq[i][0]=height[i];
for(j=1;j<20;j++)for(i=1;i+er[j-1]-1<=n;i++)rmq[i][j]=min(rmq[i][j-1],rmq[i+er[j-1]][j-1]);
}
int LCP(int a,int b){
int x=rank[a],y=rank[b],t;
if(x>y)t=x,x=y,y=t;
x++;
int k=log2[y-x+1];
return min(rmq[x][k],rmq[y-er[k]+1][k]);
}
int main(){
scanf("%s",s);
n=strlen(s);
s[n]=0;
GetSA(s,sa,n+1,128);
CalHeight(s,sa,n);
//RMQ();
for(int i=1;i<=n;i++)printf("%d ",sa[i]+1);
putchar('\n');
for(int i=2;i<=n;i++)printf("%d ",height[i]);
return 0;
}
评论 (0)
