(Adapted from the MIUP’2011)
Burrow and Wheeler discovered in 1994 a clever but simple way to achieve very nice compression ratios when compressing blocks of data.
Basically, they propose a very simple procedure to pre-process the blocks to be compressed returning a convenient word that enables simple compression methods to be used that give good compresson rates.
Let us look at an example.
Imagine that you want to compress the word abracadabra.
Burrow and Wheeler propose to compute the set of all the possible
rotations (right to left rotations) of the word to be compressed. This
Then they propose to order (using the natural lexicographic order) this list and to look at the word composed by the letters of the last column. The rotation set is now the following:
and the resulting rotated word is rdarcaaaabb.
Surprisingly enough this process tends to gather the same letters in the same part of the resulting word (and this then offers a very competitive compression ratio using very simple algorithms).
But more interesting is the following fact: there is an efficient way to recover the original word abacadabra by knowing only the word rdarcaaaabb and the position of the original word abacadabra in the rotation list that gave rdarcaaaabb, i.e. position 2.
Your task is the following: compute this transformation.
Given a word, define a program that computes and gives the rotated word and the position in the ordered rotation list of the original word.
The input consists of one line with the word to be compressed.
The maximum size of a word to be compressed is 1000.
The ascii code of the input characters is exclusively included in the interval [33..126]. This constraint ensures that the given characters are human readable characters.
The output consists of two lines.
The first line is the rotated word.
The second line contains the position (an integer) of the original word in the ordered rotation list.
This document was translated from LATEX by HEVEA.