BWT and IBWT

Burrows-Wheeler Transform and its inverse.
See this and this.

// BWT, O( N ^ 2 lg N ) due to SA
string s;
int slen;
vi sa;

bool sa_cmp( const int i, const int j ){
    return s.substr( i, slen ) < s.substr( j, slen );
}

void solve(){
    cin >> s;
    slen = s.size();
    sa = vi( slen );
    s += s;
    for( int i = 0; i < slen; ++i )
        sa[ i ] = i;
    stable_sort( sa.begin(), sa.end(), sa_cmp );
    for( int i = 0; i < slen; ++i )
        cout << s[ ( sa[ i ] + slen - 1 ) % slen ];
}

// IBWT, O( N )
string s;
int slen;
vi nxt;

void solve(){
    cin >> s;
    slen = s.size();
    nxt = vi( slen );
    vvi idx( 256 );
    for( int i = 0; i < slen; ++i )
        idx[ s[ i ] ].push_back( i );
    for( int i = 0, c = 0; i < 256; ++i )
        for( int j = 0; j < idx[ i ].size(); ++j )
            nxt[ c++ ] = idx[ i ][ j ];
    vector< char > ans;
    for( int i = 0, p = 0; i < slen; ++i )
        ans.push_back( s[ p = nxt[ p ] ] );
    for( int i = 1; i < ans.size(); ++i )
        cout << ans[ i ];
    cout << ans[ 0 ];
}