#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define B(x) (1<<(x))
typedef long long ll;
const int oo=0x3f3f3f3f;
const ll OO=1LL<<61;
const int MOD=10007;
const int maxn=400005;
int rank[maxn],SA[maxn],height[maxn];
int t1[maxn],t2[maxn],t3[maxn],t4[maxn];
int ss[maxn];

void Swap(int*& x,int*& y){

    int *temp=x;
    x=y;
    y=temp;
}

bool cmp(int t[],int a,int b,int l){

    return t[a]==t[b]&&t[a+l]==t[b+l];
}

bool cp(int a,int b){

    return ss[a]<ss[b];
}

void build_SA(int s[],int len,int up){

    int *k1=t1,*k2=t2,*r=t3,*cnt=t4;
    for(int i=0;i<len;i++)k2[i]=i;
    sort(k2,k2+len,cp);
    for(int i=0;i<len;i++)SA[i]=k2[i];
    k1[SA[0]]=0;
    int p=1;
    for(int i=1;i<len;i++){
        k1[SA[i]]= s[SA[i]]==s[SA[i-1]] ? p-1 : p++;
    }
    up=p;
    p=1;
    for(int d=1;p<len;d<<=1,up=p){

        p=0;
        for(int i=len-d;i<len;i++)k2[p++]=i;
        for(int i=0;i<len;i++)if(SA[i]>=d)k2[p++]=SA[i]-d;
        for(int i=0;i<len;i++)r[i]=k1[k2[i]];

        for(int i=0;i<up;i++)cnt[i]=0;
        for(int i=0;i<len;i++)cnt[r[i]]++;
        for(int i=1;i<up;i++)cnt[i]+=cnt[i-1];
        for(int i=len-1;i>=0;i--)SA[--cnt[r[i]]]=k2[i];

        Swap(k1,k2);
        k1[SA[0]]=0;
        p=1;
        for(int i=1;i<len;i++){
            k1[SA[i]]= cmp(k2,SA[i-1],SA[i],d) ? p-1 : p++;
        }
    }
}

void get_height(int s[],int len){

    for(int i=1;i<=len;i++)rank[SA[i]]=i;
    for(int i=0,p=0;i<len;i++){

        int j=SA[rank[i]-1];
        while(s[i+p]==s[j+p])p++;
        height[rank[i]]=p;
        if(p)p--;
    }
}

void output(int out[],int s,int e){

    for(int i=s;i<=e;i++){
        printf("%d\n",out[i]);
    }
}

int main(){

    int n,e,start;
    scanf("%d",&n);
    for(int i=n-1;i>=0;i--)scanf("%d",&ss[i]);
    ss[n]=-oo;
    build_SA(ss,n+1,-1);
    get_height(ss,n);
    for(int i=1;i<=n;i++){
        if(SA[i]>=2){
            start=SA[i];
            break;
        }
    }
    output(ss,start,n-1);
    e=start;
    n=e;
    for(int i=0;i<e;i++)ss[n++]=ss[i];
    ss[n]=-oo;
    build_SA(ss,n+1,-1);
    get_height(ss,n);
    for(int i=1;i<=n;i++){
        if(SA[i]<e&&SA[i]>=1){
            start=SA[i];
            break;
        }
    }
    output(ss,start,e-1);
    output(ss,0,start-1);
    return 0;
}
/**
4
10000
2
1000
6

3
3 2 1
*/

• Re:贴个ac代码 (2828) PhantoM__ 2018-08-18 15:36:54
• Re:贴个ac代码 (27) PhantoM__ 2018-08-18 15:37:42