Burrows-Wheeler Transform

The Burrows-Wheeler transform lists all cyclic rotations of a string, sorts them lexicographically, and reads off the last column together with the row index of the original string.