Burrows-Wheeler Transform without EOF character
algorithm, burrows-wheeler-transform, sorting, string
Solution
You can perform the transform in linear time and space without the EOF character by computing the suffix array of the string concatenated with itself. Then iterate over the suffix array. If the current suffix array value is less than `n`, add to your output array the last character of the rotation starting at the position denoted by the current value in the suffix array. This approach will produce a slightly different BWT transform result, however, since the string rotations aren't sorted as if the EOF character were present.
A more thorough description can be found here: http://www.quora.com/Algorithms/How-I-can-optimize-burrows-wheeler-transform-and-inverse-transform-to-work-in-O-n-time-O-n-space
Problem
I need to perform a well-known Burrows-Wheeler Transform in linear time. I found a solution with suffix sorting and EOF character, but appending EOF changes the transformation. For example: consider the string `bcababa` and two rotations - s1 = `abababc` - s2 = `ababcab` it's clear that s1 < s2. Now with an EOF character: - s1 = ababa#bc - s2 = aba#bcab and now s2 < s1. And the resulting transformation will be different. How can I perform BWT without EOF?