Burrows-Wheeler-Transformation

• Time : $O(|s|^2log|s|)$
• Space : $O(|s|^2)$

c++

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

std::pair<std::string, int> encode(std::string s) {
    if (s.empty()) return {"", 0};
    std::vector<std::string> l;
    for (int i = 0; i < s.length(); ++i) {
        l.push_back(s.substr(s.length() - i, i) + s.substr(0, s.length() - i));
    }
    std::sort(l.begin(), l.end());
    int idx = 0;
    for (int i = 0; i < l.size(); ++i) {
        if (l[i] == s) {
            idx = i;
            break;
        }
    }
    std::string res;
    for (const auto& x : l) {
        res += x.back();
    }
    return {res, idx};
}

std::string decode(std::string s, int n) {
    if (s.empty()) {
        return s;
    }
    std::vector<std::string> l(s.length());
    for (int i = 0; i < s.length(); ++i) {
        for (int j = 0; j < s.length(); ++j) {
            l[j] = s[j] + l[j];
        }
        std::sort(l.begin(), l.end());
    }
    return l[n];
}