Построение суффиксного массива с помощью стандартных методов сортировки

Построение суффиксного массива

Согласно определению суффиксного массива, для его построения достаточно отсортировать все суффиксы строки. Заменим сортировку суффиксов строки [math]\alpha[/math] на сортировку циклических сдвигов строки [math]\alpha\$[/math], где символ [math]\$[/math] строго меньше любого символа из [math]\alpha[/math]. Тогда если в упорядоченных циклических сдвигах отбросить суффикс, начинающийся на [math]\$[/math], то получим упорядоченные суффиксы исходной строки [math]\alpha[/math]. В дальнейшем положим [math]|\alpha\$| = N [/math] (заметим, что все циклические сдвиги также длины [math]N[/math]).

Алгоритм за [math]\bold{O(N^2 log(N))}[/math]

Данный алгоритм достаточно тривиален. Отсортируем все циклические сдвиги строки [math]\alpha\$[/math] воспользовавшись любым известным ранее методом логарифмической сортировки (например "сортировка слиянием"). Тогда время на сравнение любых двух циклических сдвигов будет осуществляться за [math]O(N)[/math] и суммарная сложность алгоритмы составит [math]O(N^2\log(N))[/math].