Suffix Array…

好不容易写了个SA的代码,以前写过但是忘掉了囧。。。
Code:
#include<cstdio>#include<algorithm>#include<iostream>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=10000+10;char C[maxn];int n,sa[maxn],ta[maxn],tb[maxn],m,tv[maxn];void sort(int*x,int*y,int m){ static int w[maxn]; rep(i,m)w[i]=0;rep(i,n)w[x[y[i]]]++; rep(i,m)if(i)w[i]+=w[i-1]; for(int i=n-1;i>=0;i–)sa[–w[x[y[i]]]]=y[i];}inline bool cmp(int*r,int i,int j,int l){ return r[i]==r[j]&&r[i+l]==r[j+l];}void Da(){ int*x=ta,*y=tb,i,j,p; rep(i,n)x[i]=C[i],tv[i]=i;sort(x,tv,m); for(j=1,p=1;p<n;j*=2,m=p) { for(p=0,i=n-j;i<n;i++)y[p++]=i; rep(i,n)if(sa[i]>=j)y[p++]=sa[i]-j;sort(x,y,m); for(swap(x,y),p=1,x[sa[0]]=0,i=1;i<n;i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; }}int main(){ scanf("%s",C);n=strlen(C);C[n++]=0;m=’Z’+1; Da(); rep(i,n)printf("%dn",sa[i]);}

One thought on “Suffix Array…

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>