Template Suffix Array

The first doubling SA that worked...
This post will be updated soon.

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

const int MAXN = 1e4 + 4;

char s[ MAXN ];

struct suffix_array{ // O( N lg N lg N )
  int n;
  vector< int > sa;
  suffix_array( const char *s ) : n( strlen(s) ), sa( n ) { 
    vector< int > r( n ), t( n ); 
    for( int i = 0; i < n; ++i ) r[ sa[ i ] = i ] = s[ i ];
    for( int h = 1; t[ n - 1 ] != n - 1; h *= 2) {
      auto cmp = [&](int i, int j) {
        if( r[ i ] != r[ j ]) return r[ i ] < r[ j ];
        return i + h < n && j + h < n ? r[ i + h ] < r[ j + h ] : i > j;
      };
      sort( sa.begin(), sa.end(), cmp );
      for(int i = 0; i + 1 < n; ++i ) t[ i + 1 ] = t[ i ] + cmp( sa[ i ], sa[ i + 1 ] );
      for(int i = 0; i < n; ++i )     r[ sa[ i ] ] = t[ i ];
    }
  }
  int operator[]( int i ) const{ return sa[ i ]; }
};

int main() {
  scanf( "%s", s );
  suffix_array sary( s );
  for( int i = 0; i < sary.n; ++i ) 
    printf( "%d%c", sary[i], " \n"[ i + 1 == sary.n ] );
}