Я попытался вращать действительно большую строку в массиве циклических строк burrow Wheelers.
Но мой ввод составляет около 200000 символов, и когда ввод такой большой, я не могу запустить код, так как ему не хватает места в куче.
Мой профессор сказал, что единственный способ реализовать это - линейный объем памяти. Что я понятия не имею, что это значит.
Могу ли я узнать, какие еще способы создать циклическую строку, которая эффективно использует память, и использовать ее без нехватки памяти?
Уловка для сокращения использования памяти заключается в создании кругового массива суффиксов, что может быть сделано за время, пропорциональное n lg n в среднем случае (и память, пропорциональная n), используя вариант быстрой сортировки, который рассматривает каждый символ в строке отдельно (он же 3). -way Быстрая сортировка строк; концептуально она похожа на сортировку по основанию).
Когда даже это занимает слишком много памяти, вам нужно ограничить преобразование Берроуза-Уилера для работы с блоками фиксированного размера (выполнить кодирование X символов, затем следующих X символов и т. д., пока вы не закодируете всю строку, обращая процесс расшифровки).
