Burrows-Wheeler Transform. Should optimize it sometime...

gistfile1.cpp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

namespace {
    std::string rotl(const std::string &s) {
        return s.substr(1) + s.at(0);
    }
}

std::string bwt(const std::string &s) {
    std::vector<std::string> rots;
    rots.reserve(s.size());
    rots.push_back(s);

    for (int i = 1; i < s.size(); ++i)
        rots.push_back(rotl(rots[i - 1]));

    std::sort(rots.begin(), rots.end());
    std::string lastCol(rots.size(), ' ');

    for (int i = 0; i < rots.size(); ++i)
        lastCol[i] = rots[i][rots[i].size() - 1];

    return lastCol;
}

std::string inv_bwt(const std::string &s) {
    std::vector<std::string> v(s.size(), "");

    for (int i = 0; i < s.size(); ++i) {
        for (int a = 0; a < s.size(); ++a)
            v[a] = s[a] + v[a];

        std::sort(v.begin(), v.end());
    }

    for (int i = 0; i < v.size(); ++i) {
        if (v[i][v.size() - 1] == '\x7f')
            return v[i];
    }

    return s;
}

int main() {
    std::string so = "mathias mathias mathias       mathias maaaaaaathias\x7f";
    std::size_t rep_count = 40;
    std::string s;
    for (int i = 0; i < rep_count; ++i)
        s += so;
    inv_bwt(bwt(s));
}