Изменения

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

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

'''ret''' 0

Данный алгоритм является некоторым улучшением предыдущего. Основная цель {{---}} сократить оценку времени сравнения двух циклических сдвигов до <tex>O(\log(n))</tex>, тогда мы по аналогии с предыдущим алгоритмом получим оценку <tex>O(N \log^2(N))</tex>. У нас есть возможность быстро сравнивать подстроки на равенство используя метод, описанный [[Поиск_подстроки_в_строке_с_использованием_хеширования._Алгоритм_Рабина-Карпа | здесь]].

'''ret''' <tex>l</tex>

Этот алгоритм сильно отличается от двух предыдущих и от него несложно перейти к алгоритму за <tex>O(N \log(N))</tex>. Итак, основная идея: на каждом шаге будем сортировать префиксы циклических сдвигов длины <tex>1,2,4,..., 2^{\lceil \log_2(n)\rceil}</tex>. Еще одно важное дополнение: после каждой фазы каждому префиксу циклического сдвига <tex>s[i..i-1]</tex> будет присваиваться номер класса эквивалентности <tex>c[i]</tex> среди этих префиксов. Причем классы эквивалентности должны быть пронумерованы в лексикографическом порядке соответствующих представителей.