Burrows-Wheeler transform utilities

Burrows-Wheeler transform

This computes \(BWT_s[0..n-1]\) for the given string \(s[0..n-1]\). The transform is defined as follows. Let \(S[0..n-1]\) be the sorted list of cyclical rotations of \(s\). Then \(BWT_s[i] = S[i - 1 \mod n]\). If you want the transform to be invertible, add a unique symbol to the end of the string.
Enter input text \(s\)

Burrows-Wheeler transform inversion

This computes a string \(s[0..n-1]\) that transforms to a given \(BWT_s[0..n-1]\). The result is unique only up to rotation. The starting point \(k\) specifies the suffix to start inverting from.
Enter \(BWT_s[0..n-1]\)

Position \(k\) to start from:

Suffix array

This computes the array of lexicographically sorted suffixes.
Enter \(s[0..n-1]\)

Note: these implementations are asymptotically inefficient ( \(O(n^3), O(n^2) \) and \(O(n^3)\), respectively). For illustrative purposes only.