Изменения

Перейти к: навигация, поиск
стиль
== Идея построения суффиксного массива ==
Согласно [[Суффиксный массив|определению]] суффиксного массива, для его построения достаточно отсортировать все суффиксы строки. Заменим сортировку суффиксов строки <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>.
== Алгоритм за O(N^2 log(N)) (наивно) ==
Данный алгоритм достаточно тривиален. Отсортируем все циклические сдвиги строки <tex>\alpha\$</tex> , воспользовавшись любым известным ранее методом логарифмической сортировки (например "сортировка слиянием"). Тогда сравнение любых двух циклических сдвигов будет осуществляться за <tex>O(N)</tex> и суммарная сложность алгоритма составит <tex>O(N^2\log(N))</tex>.
=== Псевдокод ===
== Алгоритм за O(N log^2(N)) (хеши) ==
Данный алгоритм является некоторым улучшением предыдущего. Основная цель {{- --}} сократить оценку времени сравнения двух циклических сдвигов до <tex>O(\log(n))</tex>, тогда мы по аналогии с предыдущим алгоритмом получим оценку <tex>O(N \log^2(N))</tex>. У нас есть возможность быстро сравнивать подстроки на равенство подстроки используя метод, описанный [[Поиск_подстроки_в_строке_с_использованием_хеширования._Алгоритм_Рабина-Карпа | здесь]].
Далее пусть Пусть нам необходимо сравнить два циклических сдвига <tex>s[i_1..i_1-1]</tex> и <tex>s[i_2..i_2-1]</tex>. Найдем сначала их наибольший общий префикс (<tex>lcp(i_1,i_2)</tex>), для этого будем использовать двоичный поиск по длине совпадающего префикса, а проверку осуществлять с помощью посчитанных хешей префиксов.
 Если оказалось, что <tex>lcp(i_1,i_2) = N</tex>, то строки равны. Если же <tex>lcp(i_1,i_2) < N</tex>, то символы <tex>s[i_1 + lcp]</tex> и <tex>s[i_2+lcp]</tex> точно различаются, и их сравнение позволяет сделать вывод, какой из циклических сдвигов меньше в лексикографическом порядке. Итак, двоичный поиск работает за <tex>O(\log(N))</tex> , остальные операции требуют константного времени, получаем оценку времениследовательно, время, необходимого необходимое на сравнение двух циклических сдвигов , оценивается как <tex>O(\log(N))</tex>.
=== Псевдокод ===
== Алгоритм за O(N log^2(N)) (префиксы циклических сдвигов) ==
Этот алгоритм сильно отличается от двух предыдущих и от него не сложно несложно перейти к алгоритму за <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> среди этих префиксов. Причем классы эквивалентности должны быть пронумерованы в лексикографическом порядке соответствующих представителей.
В начале Сначала легко можно отсортировать за <tex>O(N \log(N))</tex> префиксы длины <tex>1</tex>, т.е. то есть символы. А номера классов поставить в соответствии с порядковым номером символа в алфавите.
Рассмотрим теперь переход от префиксов длины <tex>l</tex> к префиксам длины <tex>2l</tex>. Научимся сравнивать два префикса длины <tex>2l</tex> за <tex>O(1)</tex>: Пусть даны префиксы <tex>s[i..i+2l-1]</tex>, <tex>s[j..j+2l-1]</tex>, сравним сначала их левые половинки, использовав значения <tex>c[i], c[j]</tex> с предыдущего шага, если <tex>c[i]\neq c[j]</tex>, то префиксы соотносятся так как же, как <tex>c[i]</tex> и <tex> c[j]</tex>, если <tex>c[i]=c[j]</tex>, то переходим к сравнению <tex>c[i+l]</tex> и <tex> c[j+l]</tex>. Итак, отсортировать префиксы длины <tex>2l</tex> можно за <tex>O(N\log(n))</tex>. Вычислить новые <tex>c[i]</tex> можно легко просто пробежавшись в лексикографическом порядке по префиксам, и увеличивая значение номер соответствующего класса на <tex>1</tex> , если текущий префикс не совпадает с предыдущим (сравнивать с помощью старых <tex>c[i], c[i+l]</tex>).
После шага <tex>l =2^{\lceil \log_2(n)\rceil} \ge N</tex>. Все все циклические сдвиги будут отсортированы. Всего шагов <tex>O(\log(N))</tex>, каждый шаг проводится за <tex>O(N \log(n))</tex>, итоговая асимптотика <tex>O(N \log^2(N))</tex>.
=== Псевдокод ===
53
правки

Навигация