ix. Burrows-Wheeler Transform

$\mathrm{BWT}(s)$ = last column of the sorted rotations of $s\#$ ($\#$ a unique smallest sentinel), computable from the suffix array: $\mathrm{BWT}[i]=t[\mathrm{sa}[i]-1]$. It clusters equal characters (good for RLE + move-to-front: bzip2), is invertible by the LF-mapping, and with rank queries becomes the FM-index: count occurrences of $p$ by backward search in $O(|p|)$ (DNA aligners). Uses sais from Suffix Array. CSES 1113 String Transform is inverseBwt.

Use	How	Cost
transform	suffix array of $s\#$	$O(n)$ with SA-IS
inverse	LF mapping: stable sort of positions by character	$O(n\log n)$ or $O(n+\sigma )$ counting
count occurrences of $p$ (FM-index)	backward search with $C[c]$ and $\mathrm{occ}(c,i)$	$O(|p|)$ with an $O(n\sigma )$ table (wavelet tree: $O(|p|\log \sigma )$, $O(n\log \sigma )$ bits)
locate occurrences	SA entries of the final interval (sampled SA in practice)	$O(\text{occ})$
compressibility	number of BWT runs $r$; LZ77 factors $z\le r$
compression pipeline	BWT $\to$ move-to-front $\to$ RLE / entropy coding

string bwt(const string& s) {                               // s must not contain '#'; result has exactly one '#'
    vector<int> v(sz(s) + 1, 0); for (int i = 0; i < sz(s); i++) v[i] = (unsigned char)s[i] + 1;
    vector<int> sa = sais(v, 257); int n = sz(v);
    string t = s + '#', res(n, ' ');
    for (int i = 0; i < n; i++) res[i] = t[(sa[i] + n - 1) % n];
    return res;
}
string inverseBwt(const string& b) {                        // LF mapping
    int n = sz(b); vector<int> nxt(n); iota(all(nxt), 0);
    auto key = [](char c) { return c == '#' ? -1 : (int)(unsigned char)c; };
    stable_sort(all(nxt), [&](int x, int y) { return key(b[x]) < key(b[y]); });   // row r's first char is b[nxt[r]]
    string res; int i = nxt[0];
    for (int k = 0; k + 1 < n; k++) { i = nxt[i]; res += b[i]; }
    return res;
}
struct FMIndex {                                            // lowercase text
    string b; vector<int> sa, C; vector<array<int, 27>> occ;   // occ[i][c] = #c in b[0, i), c = 0 for '#'
    FMIndex(const string& s) {
        vector<int> v(sz(s) + 1, 0); for (int i = 0; i < sz(s); i++) v[i] = s[i] - 'a' + 1;
        sa = sais(v, 27); int n = sz(v); b.assign(n, ' ');
        for (int i = 0; i < n; i++) { int j = (sa[i] + n - 1) % n; b[i] = j == n - 1 ? '#' : s[j]; }
        occ.assign(n + 1, {}); for (int i = 0; i < n; i++) { occ[i + 1] = occ[i]; occ[i + 1][b[i] == '#' ? 0 : b[i] - 'a' + 1]++; }
        C.assign(28, 0); for (int c = 0; c < 27; c++) C[c + 1] = C[c] + occ[n][c];
    }
    pair<int, int> range(const string& p) const {           // SA rows [lo, hi) whose suffixes start with p
        int lo = 0, hi = sz(b);
        for (int i = sz(p) - 1; i >= 0 && lo < hi; i--) { int c = p[i] - 'a' + 1; lo = C[c] + occ[lo][c]; hi = C[c] + occ[hi][c]; }
        return {lo, hi};
    }
    int count(const string& p) const { auto [lo, hi] = range(p); return max(0, hi - lo); }
    vector<int> locate(const string& p) const { auto [lo, hi] = range(p); vector<int> r; for (int i = lo; i < hi; i++) r.push_back(sa[i]); sort(all(r)); return r; }
};
vector<int> moveToFront(const string& s) { vector<int> order(256); iota(all(order), 0); vector<int> out; for (unsigned char c : s) { int i = find(all(order), (int)c) - order.begin(); out.push_back(i); order.erase(order.begin() + i); order.insert(order.begin(), c); } return out; }
string inverseMoveToFront(const vector<int>& v) { vector<int> order(256); iota(all(order), 0); string s; for (int i : v) { int c = order[i]; s += char(c); order.erase(order.begin() + i); order.insert(order.begin(), c); } return s; }

Proof: the BWT, its inverse and backward search

From the SA. The rotations of $t=s\#$ sorted lexicographically are in suffix order, because $\#$ is unique and smallest (comparison stops at the sentinel); the last character of the rotation starting at $\mathrm{sa}[i]$ is $t[\mathrm{sa}[i]-1]$. LF-mapping. The $k$-th occurrence of character $c$ in the last column (BWT) and the $k$-th occurrence of $c$ in the first column are the same text position: rows ending in $c$, rotated by one, start with $c$ and keep their relative order (it is decided by what follows $c$). So the stable sort of row indices by BWT character maps each row of the first column to the row whose last character it is; the code’s nxt[r] is the row of the next rotation, and walking from the row of $\#$ spells $s$. Backward search. If the rows prefixed by $w$ form $[lo,hi)$, the rows prefixed by $cw$ are $[C[c]+\mathrm{occ}(c,lo),C[c]+\mathrm{occ}(c,hi))$: $C[c]$ counts rows starting with a smaller character, and among rows starting with $c$ the order is that of the following suffixes, i.e. of the rows in $[lo,hi)$ whose BWT character is $c$, by the LF argument. Move-to-front is a bijection (the decoder maintains the same list). Checked: round trips, FM counts against find, locations against brute force.

Related notes

• Suffix Array
• Range Order Statistics (wavelet trees for rank queries)
• Lyndon Words (bijective BWT)