题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1031
求字符串排名的问题,直接上后缀数组。
由于这个字符串是环形的,我们把它倍增一下就好了。然后发现其实就是求sa数组裸题,后缀长度大于等于len的后缀就可以对应原来的一种字符串,直接输出就好了……
1 #include2 #include 3 #include 4 using namespace std; 5 int n,m; 6 char s[200010]; 7 int rk[200010],sa[200010],tmp[200010],c[200010]; 8 bool inline cmp(int *r,int a,int b,int l){ 9 return r[a]==r[b]&&r[a+l]==r[b+l];10 }11 void Getsa(){12 m=300;13 for(int i=0;i<=m;i++) c[i]=0;14 for(int i=1;i<=n;i++) c[rk[i]=s[i]]++;15 for(int i=1;i<=m;i++) c[i]+=c[i-1];16 for(int i=n;i>=1;i--) sa[c[rk[i]]--]=i;17 int p;18 for(int i=1;i<=n;i<<=1){19 p=0;20 for(int j=n-i+1;j<=n;j++) tmp[++p]=j;21 for(int j=1;j<=n;j++) if(sa[j]>i) tmp[++p]=sa[j]-i;22 for(int j=0;j<=m;j++) c[j]=0;23 for(int j=1;j<=n;j++) c[rk[tmp[j]]]++;24 for(int j=1;j<=m;j++) c[j]+=c[j-1];25 for(int j=n;j>=1;j--) sa[c[rk[tmp[j]]]--]=tmp[j];26 swap(rk,tmp);27 rk[sa[1]]=p=1;28 for(int j=2;j<=n;j++) rk[sa[j]]=cmp(tmp,sa[j],sa[j-1],i)?p:++p;29 if(p>=n) break;30 m=p;31 }32 }33 int main(){34 scanf("%s",s+1);35 int len=strlen(s+1);36 for(int i=1;i