首页 > 代码库 > 【tyvj1860】后缀数组

【tyvj1860】后缀数组

2024-09-11 22:14:26   206人阅读

描述

我们定义一个字符串的后缀suffix(i)表示从s[i]到s[length(s)]这段子串。
后缀数组（Suffix array）SA[i]中存放着一个排列，满足suffix(sa[i])<suffix(sa[i+1]) 按照字典序方式比较
定义height[i]表示suffix(sa[i])与suffix(sa[i-1])之间的最长公共前缀长度，其中height[1]=0
你的任务就是求出SA和height这两个数组。字符串长度<=200000

输入格式

一行，为描述中的字符串（仅会出现小写字母）

输出格式

共两行，每行n个数，第一行为sa[i]，第二行为height[i]，其中每行的数均用空格隔开

测试样例1

输入

aabaaaab

输出

4 5 6 1 7 2 8 3 
0 3 2 3 1 2 0 1
后缀数组模板题
随便贴一个写得很丑的模板
以后要把它背下来啊啊啊
QAQ
技术分享
 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 using namespace std; 6 const int N=200050; 7 int Sa[N],wu[N],wv[N],wa[N],wb[N],R[N],Rank[N],Height[N],rank[N]; 8 char s[N]; 9 int cmp(int *r,int a,int b,int l){return r[a]==r[b] && r[a+l]==r[b+l];}10 inline void SA(int *r,int *sa,int n,int m){11     int *x=wa,*y=wb;12     for(int i=0;i<m;++i)wu[i]=0;13     for(int i=0;i<n;++i)++wu[x[i]=r[i]];14     for(int i=1;i<m;++i)wu[i]+=wu[i-1];15     for(int i=n-1;i>=0;--i)sa[--wu[x[i]]]=i;16     for(int j=1,p=0;p<n;j<<=1,m=p){17         p=0;18         for(int i=n-j;i<n;++i)y[p++]=i;19         for(int i=0;i<n;++i)if(sa[i]>=j)y[p++]=sa[i]-j;20         for(int i=0;i<m;++i)wu[i]=0;21         for(int i=0;i<n;++i)++wu[wv[i]=x[y[i]]];22         for(int i=0;i<m;++i)wu[i]+=wu[i-1];23         for(int i=n-1;i>=0;--i)sa[--wu[wv[i]]]=y[i];24         swap(x,y);25         p=1;26         x[sa[0]]=0;27         for(int i=1;i<n;++i)x[sa[i]]=((y[sa[i]]==y[sa[i-1]]) && y[sa[i]+j]==y[sa[i-1]+j]) ? p-1 : p++;28     }29 }30 inline void Get_Height(int *r,int n){31     for(int i=1;i<=n;++i)rank[Sa[i]]=i;32     for(int i=0,j=0,k=0;i<n;Height[rank[i++]]=k)33         for(k?--k:0,j=Sa[rank[i]-1];r[i+k]==r[j+k];++k);34 }35 inline void output(int x){36     if(!x)return;output(x/10);37     putchar((x%10)+‘0‘);38 }39 int main(){40     scanf("%s",s);41     int len=strlen(s);42     for(int i=0;i<len;++i)R[i]=s[i]-‘a‘+1;43     R[len]=0;44     SA(R,Sa,len+1,30);45     Get_Height(R,len);46     for(int i=1;i<=len;++i)output(Sa[i]+1),putchar(‘ ‘);puts("");47     for(int i=1;i<=len;++i){48         if(!Height[i])putchar(‘0‘);49         else output(Height[i]);putchar(‘ ‘);50     }puts("");51     return 0;52 }
tyvj1860

 

【tyvj1860】后缀数组


联系
我们