# 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.