Хотя вы можете построить массив суффиксов из дерева суффиксов, в этом нет особого смысла. Это исключило бы главное преимущество массива суффиксов (помимо общей простоты): незначительное потребление памяти.
Существует простой способ сортировки массива суффиксов за O(n*logn) время. (По этой причине он часто используется во всех видах конкурсов алгоритмов как альтернатива сложным попыткам суффиксов)
Основная идея заключается в следующем. Мы будем сортировать суффиксы поэтапно, а на этапе i (i = 0, 1, 2, 3, ...) учитываются только первые 2^i символов каждого суффикса.
Сортировка суффиксов по первому символу тривиальна и не должна быть для вас проблемой. После этого («0-го») этапа мы будем иметь частично отсортированный массив суффиксов и еще один массив, содержащий разбиение суффиксов на сегменты: каждый блок содержит суффиксы с одинаковым первым символом.
Теперь представьте, что мы уже закончили стадию i и теперь имеем дело со стадией i + 1. Нам нужно сравнить два суффикса s(t) и s(q), принадлежащих одному и тому же сегменту. (Пусть s(t) будет суффиксом, начинающимся с позиции t в исходной строке.)
Поскольку первые 2^i символов для них одинаковы, нам нужно учитывать только следующие 2^i символов (поэтому общая сумма будет 2^(i+1)). Но суффикс s(t) без первых символов 2^i равен s(t + 2^i). Поэтому нам нужно только сравнить s(t + 2^i) и s(q + 2^i) в соответствии с их первыми 2^i символами, и у нас уже есть эта информация со стадии i.
Конец. Реализация этого в первый раз может быть немного сложнее (тоже хорошее упражнение), но это идея. Обратите внимание, что единственный раз, когда мы читаем реальные символы из исходной строки, это шаг 0. Затем на шаге i мы используем только результат шага i - 1.
редактировать
Эта оригинальная статья 1989 года представляет эту идею более подробно. (Гораздо больше деталей, чем необходимо, чтобы понять это, а реализация сложнее, чем нужно, ИМХО.)