Я не гуру, но сдаётся мне, что O(n2) — вполне достойно, по-крайней мере в той формулировке, что я понял. Ведь результатом должен быть отсортированный массив строк размером от n (исходная строка «аа… а») до (1+n)*n/2 (исходная строка «abcd..»). С введением ограничения на размер подстроки, быть может, получится и улучшить эффективность алгоритма.
А вообще, как говорил Пайк:
Правило 3: Изощрённые алгоритмы являются медленными, если n мало, а n обычно мало. В изощрённых алгоритмах присутствуют большие константы. До тех пор, пока вы не убедитесь, что n часто становится большим, избегайте изощрённости. (Даже если n становится большим, вначале используйте правило 2).