Изменения
Новая страница: «== Построение суффиксного массива == Согласно определению суффиксног…»
== Построение суффиксного массива ==
Согласно [[Суффиксный массив|определению]] суффиксного массива, для его построения достаточно отсортировать все суффиксы строки. Заменим сортировку суффиксов строки <tex>\alpha</tex> на сортировку циклических сдвигов строки <tex>\alpha\$</tex>, где символ <tex>\$</tex> строго меньше любого символа из <tex>\alpha</tex>. Тогда если в упорядоченных циклических сдвигах отбросить суффикс, начинающийся на <tex>\$</tex>, то получим упорядоченные суффиксы исходной строки <tex>\alpha</tex>. В дальнейшем положим <tex>|\alpha\$| = N </tex> (заметим, что все циклические сдвиги также длины <tex>N</tex>).
== Алгоритм за <tex>\bold{O(N^2 log(N))}</tex> ==
Данный алгоритм достаточно тривиален. Отсортируем все циклические сдвиги строки <tex>\alpha\$</tex> воспользовавшись любым известным ранее методом логарифмической сортировки (например "сортировка слиянием"). Тогда время на сравнение любых двух циклических сдвигов будет осуществляться за <tex>O(N)</tex> и суммарная сложность алгоритмы составит <tex>O(N^2\log(N))</tex>.
Согласно [[Суффиксный массив|определению]] суффиксного массива, для его построения достаточно отсортировать все суффиксы строки. Заменим сортировку суффиксов строки <tex>\alpha</tex> на сортировку циклических сдвигов строки <tex>\alpha\$</tex>, где символ <tex>\$</tex> строго меньше любого символа из <tex>\alpha</tex>. Тогда если в упорядоченных циклических сдвигах отбросить суффикс, начинающийся на <tex>\$</tex>, то получим упорядоченные суффиксы исходной строки <tex>\alpha</tex>. В дальнейшем положим <tex>|\alpha\$| = N </tex> (заметим, что все циклические сдвиги также длины <tex>N</tex>).
== Алгоритм за <tex>\bold{O(N^2 log(N))}</tex> ==
Данный алгоритм достаточно тривиален. Отсортируем все циклические сдвиги строки <tex>\alpha\$</tex> воспользовавшись любым известным ранее методом логарифмической сортировки (например "сортировка слиянием"). Тогда время на сравнение любых двух циклических сдвигов будет осуществляться за <tex>O(N)</tex> и суммарная сложность алгоритмы составит <tex>O(N^2\log(N))</tex>.
