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.