题目大意

给出一个字符串，循环字符串的起始位置，可以得到length个不同的字符串，问把这些字符串排序之后每一个字符串的第一位是什么

数据范围

字符串的长度不超过100000

题解

后缀数组模板题

程序

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define maxn 205000
using namespace std;

int sa[maxn];
int x[maxn],y[maxn],c[maxn];
char s[maxn];
int n,m;

inline void init(){
    scanf("%s",s+1);
    n=strlen(s+1);
    For(i,1,n) s[i+n]=s[i];
    n<<=1;m=128;
}

inline void suffix(){
    For(i,0,m) c[i]=0;
    For(i,1,n) ++c[x[i]=s[i]];
    For(i,1,m) c[i]+=c[i-1];
    For(i,1,n) sa[c[x[i]]--]=i;
    for(int k=1;k<n;k<<=1){
        int p=0;
        For(i,n-k+1,n) y[++p]=i;
        For(i,1,n) if (sa[i]>k) y[++p]=sa[i]-k;
        For(i,0,m) c[i]=0;
        For(i,1,n) ++c[x[y[i]]];
        For(i,1,m) c[i]+=c[i-1];
        for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i];
        m=0;
        For(i,1,n){
            int u=sa[i],v=sa[i-1];
            if ((i==1)||(x[u]!=x[v])||(x[u+k]!=x[v+k])) m++;
            y[u]=m;
        }
        if (m>=n) break;
        For(i,1,n) swap(x[i],y[i]);
    }
}

int main(){
    init();
    suffix();
    For(i,1,n) if (sa[i]<=(n>>1)) printf("%c",s[sa[i]+(n>>1)-1]);puts("");
    return 0;
}