Создание массива круговых суффиксов

Question

Для домашней задачи нам дают строку длины n, и нам говорят создать отсортированные суффиксы и отсортировать их таким образом, чтобы мы могли вернуть строку, соответствующую исходному индексу i-го индекса в отсортированном списке., Например, учитывая строку "медведи", мы имеем следующее:

!

Другими словами, значение final_index[i], равное 2, означает, что изначально суффикс в индексе 2 находится в индексе i в отсортированном списке.

Моя проблема в том, что очевидное решение - использовать подстроку и построить sorted_suffixes, а затем отсортировать их, не разрешено, потому что мы не можем явно создавать суффиксы. Как можно преодолеть это ограничение? Спасибо за помощь.

Answer 1

Используйте компаратор для сортировки суффиксов с вызовом public static void sort(T[] a, Comparator c);

Преобразовать строку в массив символов

В компараторе определите сравнение так, чтобы оно сортировало суффиксы, лексикографически сканируя по одному символу за раз... Вам не нужно явно хранить суффиксы....

Используйте все классы-оболочки вместо необработанных классов