//GET SA1
for( int i = 0 ; i < n ; i++ ) Sa[i] = db( a[i]-'a', i );
sort( Sa, Sa+n, comp );
//GET RA1
int m = ra[Sa[0].y] = 1;
for( int i = 1 ; i < n ; i++ ) ra[Sa[i].y] = ( Sa[i].x != Sa[i-1].x ) ? ++m : m;
//GET SA & RA
for( int l = 1 ; m < n ; l *= 2 ){ //Half the length of the range
// sort the second object
int yn = 0;
for( int i = n-l ; i < n ; i++ ) y[yn++] = i;
for( int i = 0 ; i < n ; i++ ) if( Sa[i].y >= l ) y[yn++] = Sa[i].y-l;
// sort the first object
for( int i = 0 ; i <= m ; i++ ) x[i] = 0;
for( int i = 0 ; i < n ; i++ ) x[ra[y[i]]]++;
for( int i = 1 ; i < n ; i++ ) x[i] += x[i-1];
for( int i = n-1 ; i >= 0 ; i-- ){
Sa[x[ra[y[i]]]-1] = db( ra[y[i]]*(m+2) + ( y[i] >= n-l ? 0 : ra[y[i]+l] ), y[i] );
x[ra[y[i]]]--;
}
// get ra value
m = ra[Sa[0].y] = 1;
for( int i = 1 ; i < n ; i++ ) ra[Sa[i].y] = ( Sa[i].x != Sa[i-1].x ) ? ++m : m;
}
for( int i = 0 ; i < n ; i++ ) ra[i]--, sa[i] = Sa[i].y;