Admin: returning hw3 written today (not earlier, I'm grading a stack).

Today I'll introduce the "Burrows Wheeler Transform" (BWT), an
application of suffix sorting that turns out to be useful in text
compression.  I expect your next (last) homework will involve
implement both the forward BWT (easy) and its inverse (trickier).

See:  BWT.java
Also it has some discussion in our book (pages 926-927) and website:
   http://algs4.cs.princeton.edu/63suffix/

We'll define the transform (see the paper!).
Some examples of the BWT:

        banana -> annb%aa
        bananamanana -> annnnmb%aaaaa

But how to transform back?  The "tabular" argument that we
can reverse this seems to be quadratic time, but we'll see
that there is a clever linear time solution.

Idea: we have string L, the last table column.  Sort it (by
counting-sort) to get F, the first column of the table.  For each
index j compute T[j], so that if L[j] is the i-th occurrence of that
character in L, then F[T[j]] is the i-th occurrence of the same
character in F.  We can compute this T array in O(N) time (like
counting-sort).  It turns out it is the "same char" in both strings.
Once we have it, we see T defines a cyclic permutation through all the
positions of F (or L), recovering the original string (in reverse).