代码

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

namespace SFX{
    int SA[200005];
    int RK[200005];
    int H [200005];
    string S; int n;
    
    void Debug(){
        for(int i = 1;i <= n;i ++) cout << RK[i] << " "; cout << "\n";
    }
    
    void init(){
        n = S.size(); int N = max( n, 26 );
        for( int i = 1; i <= n; i ++ ) RK[i] = S[i - 1] - 'a' + 1;
        for( int i = 1; i <= n; i <<= 1 ) {
            static int f[100005], s[100005], t[100005];
            memset( f, 0, sizeof(f) );
            for( int j = 1; j <= n; j ++ ) f[ RK[j + i] ] ++;
            for( int j = 1; j <= N; j ++ ) f[j] += f[j - 1];
            for( int j = 1; j <= n; j ++ ) s[ f[ RK[j + i] ] -- ] = j;
            //for( int j = 1; j <= n; j ++ ) cout << f[j] << " "; cout << "]\n";
            memset( f, 0, sizeof(f) );
            for( int j = 1; j <= n; j ++ ) f[ RK[j] ] ++;
            for( int j = 1; j <= N; j ++ ) f[j] += f[j - 1];
            for( int j = n; j >= 1; j -- ) t[ f[ RK[ s[j] ] ] -- ] = s[j];
            //for( int j = 1; j <= n; j ++ ) cout << t[j] << " "; cout << "]\n";
            int ll = -1, lr = -1, rank = 0;
            static int r[100005];
            for( int j = 1; j <= n; j ++ ) {
                if( ll != RK[ t[j] ] or lr != RK[ t[j] + i ] ) rank ++;
                r[ t[j] ] = rank;
                ll = RK[ t[j] ]; lr = RK[ t[j] + i ];
            }
            for( int j = 1; j <= n; j ++ ) RK[j] = r[j];
            if( rank == n ) break;
            //Debug();
        }
        for( int i = 1; i <= n; i ++ ) SA[ RK[i] ] = i;
        int pt = 0; S += '#';
        for( int i = 1; i <= n; i ++ ){
            if( pt ) pt --;
            int x = SA[ RK[i] - 1 ];
            while( S[ i + pt - 1 ] == S[ x + pt - 1 ] ) pt ++;
            H[ RK[i] ] = pt;
        }
    }
}

void output(){
using namespace SFX;
    for(int i = 1;i <= n;i ++) printf( "%d ", SA[i] ); putchar( '\n' ); //cout << "\n";
    for(int i = 2;i <= n;i ++) printf( "%d ", H [i] ); // cout << H [i] << " ";
}

int main(){
    cin >> SFX::S;
    SFX::init(); output();
    return 0;
}

评测结果