Our goal is to further improve on the memory requirements of the suffix array introduced in “Suffix Array of a String” for multiple pattern matching.
Given a string Text, form all possible cyclic rotations of Text; a cyclic rotation is defined by chopping off a suffix from the end of Text and appending this suffix to the beginning of Text. Next — similarly to suffix arrays — order all the cyclic rotations of Text lexicographically to form a |Text| × |Text| matrix of symbols that we call the Burrows-Wheeler matrix and denote by M(Text).
Note that the first column of M(Text) contains the symbols of Text ordered lexicographically. In turn, the second column of M(Text) contains the second symbols of all cyclic rotations of Text, and so it too represents a (different) rearrangement of symbols from Text. The same reasoning applies to show that any column of M(Text) is some rearrangement of the symbols of Text. We are interested in the last column of M(Text), called the Burrows-Wheeler transform of Text, or BWT(Text).
Although it is possible to construct the Burrows-Wheeler transform in O(|Text|) time and space, we do not expect you to implement such a fast algorithm. In other words, it is perfectly fine to produce BWT(Text) by first producing the complete Burrows-Wheeler matrix M(Text).
Implement the burrows_wheeler_transform method which takes a string which ends with a '$'.
The function should return the burrows wheeler transform of the string.
>>> burrows_wheeler_transform('ACACT$') 'T$CAAC'