首页 > 代码库 > SA模板
SA模板
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 const int M=100010; 6 char S[M]; 7 int n,i,s[M],sa[M],wa[M],wb[M],wc[M],wd[M],height[M],rank[M]; 8 bool cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];} 9 void getsa(int *r,int *sa,int n,int m){ 10 int *x=wa,*y=wb,j,p; 11 for (i=0;i<n;i++)wc[x[i]=r[i]]++; 12 for (i=1;i<m;i++)wc[i]+=wc[i-1]; 13 for (i=n-1;i>=0;i--)sa[--wc[x[i]]]=i; 14 for (j=1,p=1;p<n;j*=2,m=p){ 15 p=0; 16 for (i=n-j;i<n;i++)y[p++]=i; 17 for (i=0;i<n;i++)if (sa[i]>=j)y[p++]=sa[i]-j; 18 for (i=0;i<n;i++)wd[i]=x[y[i]]; 19 for (i=0;i<m;i++)wc[i]=0; 20 for (i=0;i<n;i++)wc[wd[i]]++; 21 for (i=1;i<m;i++)wc[i]+=wc[i-1]; 22 for (i=n-1;i>=0;i--)sa[--wc[wd[i]]]=y[i]; 23 swap(x,y);p=1;x[sa[0]]=0; 24 for (i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; 25 } 26 } 27 void getheight(int *r,int *sa,int n){ 28 int i,j,k=0; 29 for (i=1;i<=n;i++)rank[sa[i]]=i; 30 for (i=0;i<n;height[rank[i++]]=k){ 31 if(k)k--; 32 j=sa[rank[i]-1]; 33 while(r[i+k]==r[j+k])k++; 34 } 35 } 36 int main(){ 37 scanf("%s",S); 38 n=strlen(S); 39 for (i=0;i<n;i++)s[i]=S[i]-‘a‘+1; 40 s[n]=0; 41 getsa(s,sa,n+1,100); 42 getheight(s,sa,n); 43 for (i=1;i<=n;i++)printf("%d ",sa[i]+1);puts(""); 44 for (i=2;i<=n;i++)printf("%d ",height[i]);puts(""); 45 }
SA模板
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。