Problem G
Burrows-Wheeler
The Burrows-Wheeler transform is a technique for transforming a text message so that it responds well to compression techniques. Under this transform, we consider all cyclic shifts of an input string. For example, if our text was the string “arbitrary string”, then the string “rbitrary stringa” would be the result of cyclicly shifting the string one character to the left. The first character is moved to the end of the string, and all of the other characters are moved one index earlier. If a string has $n$ characters, then there are $n$ cyclic shifts of the string. The text on the left lists all cyclic shifts of the string “arbitrary string”, one per line.
arbitrary string stringarbitrary rbitrary stringa arbitrary string bitrary stringar ary stringarbitr itrary stringarb bitrary stringar trary stringarbi garbitrary strin rary stringarbit ingarbitrary str ary stringarbitr itrary stringarb ry stringarbitra ngarbitrary stri y stringarbitrar rary stringarbit stringarbitrary rbitrary stringa stringarbitrary ringarbitrary st tringarbitrary s ry stringarbitra ringarbitrary st stringarbitrary ingarbitrary str trary stringarbi ngarbitrary stri tringarbitrary s garbitrary strin y stringarbitrar
Under the Burrows-Wheeler transform, we imagine that we lexicographically sorted all these lines. The figure on the right illustrates what this would yield for the text “arbitrary string”. The original message is encoded as the right-hand column of this sorted list of cyclicly shifted copies of the input string. For example, “arbitrary string” would be encoded as “ygrrnrbitata isr”.
For this problem, you are expected to compute the Burrows-Wheeler transform for an arbitrary line of text. Of course, the transform is invertible, but we’ll let some other programmer worry about recovering the original message from your encoding.
Input
Input consists of up to $100$ messages, one per line. A message may use lowercase or uppercase letters (a–z), digits, punctuation, and spaces. Each message may be up to $100\, 000$ characters in length. Messages continue up to the end of file. The total number of input characters is no more than $2^{20}$.
Output
For each input message, output a single line that results from applying the Burrows-Wheeler transform. The validation for this problem is sensitive to both case and spacing changes.
| Sample Input 1 | Sample Output 1 |
|---|---|
arbitrary string this is the thing I was talking about |
ygrrnrbitata isr ggssseI twahnnttthkh laiibiai tuo |
