C++14(g++5.4) 解法, 执行用时: 123ms, 内存消耗: 10100K, 提交时间: 2019-10-21 23:17:35

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 5;
char tmp[maxn], s[maxn<<1];
int n, m, sa[maxn], x[maxn], y[maxn], c[maxn];
inline void get_sa(){
    m = 122;
    for( int i=1; i<=n; i++ ) ++c[x[i]=s[i]];
    for( int i=1; i<=m; i++ ) c[i] += c[i-1];
    for( int i=n; i; i-- ) sa[c[x[i]]--] = i;
    for( int k=1; k<=n; k<<=1 ){
        int num = 0;
        for( int i=n-k+1; i<=n; i++ ) y[++num] = i;
        for( int i=1; i<=n; i++ ) if(sa[i]>k) y[++num] = sa[i]-k;
        for( int i=0; i<=m; i++ ) c[i] = 0;
        for( int i=1; i<=n; i++ ) ++c[x[i]];
        for( int i=1; i<=m; i++ ) c[i] += c[i-1];
        for( int i=n; i; i-- ) sa[c[x[y[i]]]--] = y[i], y[i]=0;
        swap(x, y);
        num = x[sa[1]] = 1;
        for( int i=2; i<=n; i++ ){
            x[sa[i]] = (y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) ? num:++num;
        }
        if( num==n ) return ;
        m = num;
    }
}

int main(){
    scanf("%s", tmp);
    int len = strlen(tmp);
    n = 0;
    for( int i=0; i<len; i++ ) s[++n] = tmp[i];
    for( int i=0; i<len; i++ ) s[++n] = tmp[i];
    get_sa();
    for( int i=1; i<=n; i++ ) if(sa[i]<=len) putchar(s[sa[i]+len-1]);
    puts("");
    
    
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 284ms, 内存消耗: 6248K, 提交时间: 2019-04-12 17:20:17

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <cmath>
#include <set>
#include <string>
 
using namespace std;
 
const int N=1000000;
char str[N];
int ranks[N],tmp[N],sa[N],k;
bool cmp(int i,int j){
    if(ranks[i]!=ranks[j])return ranks[i]<ranks[j];
    return ranks[i+k]<ranks[j+k];
}
 
int main(){
    memset(ranks,-1,sizeof(ranks));
    scanf("%s",str);
    int n=strlen(str);
    for(int i=0;i<n;i++)str[i+n]=str[i];
    n<<=1;
    for(int i=0;i<=n;i++)sa[i]=i,ranks[i]=i<n?str[i]:-1;
    for(k=1;k<=n;k<<=1){
        sort(sa,sa+n,cmp);
        tmp[sa[0]]=0;
        for(int i=1;i<=n;i++)tmp[sa[i]]=tmp[sa[i-1]]+cmp(sa[i-1],sa[i]);
        for(int i=0;i<=n;i++)ranks[i]=tmp[i];
    }
    for(int i=0;i<n;i++)
        if(sa[i]<=(n>>1)-1)
            putchar(str[sa[i]+(n>>1)-1]);
}