Мне нужно выполнить известное преобразование Берроуза-Уилера за линейное время. Я нашел решение с сортировкой по суффиксу и символом EOF, но добавление EOF меняет преобразование. Например: рассмотрим строку bcababa
и два поворота
- s1 =
abababc
- s2 =
ababcab
ясно, что s1 ‹ s2. Теперь с символом EOF:
- s1 = абаба#bc
- s2 = аба#bcab
и теперь s2 ‹ s1. И результирующая трансформация будет другой. Как я могу выполнить BWT без EOF?