Изменения

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

== Алгоритм за O(N^2 log(N)) (наивно) Наивный алгоритм ==

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

'''suf_arrayint[]'''sufArray('''string''' s) suf <tex>\leftarrow \= {0, 1, \dots, |.. s|\.length}</tex> '''sort''' (suf, '''compare''') '''retreturn''' suf

'''compareorder''' compare(<tex>j_1</tex>, <tex>j_2</tex>) '''forint''' <tex>i</tex> = 0 j1, '''toint''' <tex>|s|</tex> j2) '''dofor'''i = 0 .. s.length '''if''' (s[(<tex>j_1j1 +i</tex>) '''mod''' <tex>|s|</tex>.length] > s[(<tex>j_2j2 +i</tex>) '''mod''' <tex>|s|</tex>.length]) '''return''''ret'GT'' 1 '''if''' (s[(<tex>j_1j1 +i</tex>) '''mod''' <tex>|s|</tex>.length] < s[(<tex>j_2j2 +i</tex>) '''mod''' <tex>|s|</tex>.length]) '''retreturn''' -1''LT'' '''return''''ret'EQ'' 0

== Алгоритм за O(N log^2(N)) (, использующий хеши) ==

Данный алгоритм является некоторым улучшением предыдущего. Основная цель {{- --}} сократить оценку времени сравнения двух циклических сдвигов до <tex>O(\log(n))</tex>, тогда мы по аналогии с предыдущим алгоритмом получим оценку <tex>O(N n \log^2(N)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>suf + pref</tex> исходной строки, то с помощью двух хешей префиксов исходной строки можно найти хеш <tex>suf</tex> или префикса <tex>suf</tex>. Таким образом можно найти хеш префикса циклического сдвига.

 Если оказалось, что <tex>lcp(i_1,i_2) = Nn</tex>, то строки равны. Если же <tex>lcp(i_1,i_2) < Nn</tex>, то символы <tex>s[i_1 + lcp]</tex> и <tex>s[i_2+lcp]</tex> точно различаются, и их сравнение позволяет сделать вывод, какой из циклических сдвигов меньше в лексикографическом порядке. Итак, двоичный поиск работает за <tex>O(\log(N)n)</tex> , остальные операции требуют константного времени, получаем оценку времениследовательно, время, необходимого необходимое на сравнение двух циклических сдвигов , оценивается как <tex>O(\log(N)n)</tex>.

'''suf_arrayint[]'''sufArray('''string''' s) suf <tex>\leftarrow \= {0, 1, \dots, |.. s|\.length}</tex> '''sort''' (suf, '''compare''') '''retreturn''' suf

'''order'''compare(''' (<tex>j_1</tex>int''' j1, <tex>j_2</tex>'''int''' j2) same <tex>\leftarrow</tex> = '''lcp'''(<tex>j_1</tex>j1, <tex>j_2</tex>j2) '''retif''' s[j1 + same] <tex>j_1</tex> s[j2 + same] - '''return''' ''LT'' '''else if''' s[<tex>j_2</tex> j1 + same] == s2[j2 + same] '''return''' ''EQ'' '''else''' '''return''' ''GT''

'''lcpint''' lcp(<tex>j_1</tex>j1, <tex>j_2</tex>j2) <tex>l</tex> <tex>\leftarrow</tex> <tex>= -1</tex> <tex>r</tex> <tex>\leftarrow</tex> <tex>|= s|.length +1</tex> '''while''' (<tex>r - l > 1</tex>) <tex>m</tex> <tex>\leftarrow</tex> <tex>= (r + l) / 2</tex> '''if''' (hash[<tex>j_1\dots j_1 j1 .. j1 +m</tex>] == hash[<tex>j+2\dots j_2 j2 .. j2 + m</tex>]) <tex> l \leftarrow = m </tex>

<tex> r \leftarrow = m </tex> '''retreturn''' <tex>l</tex>

== Алгоритм за O(N log^2(N)) (, использующий префиксы циклических сдвигов) ==

Этот алгоритм сильно отличается от двух предыдущих и от него не сложно несложно перейти к алгоритму за <tex>O(N n \log(N)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 n \log(N)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(Nn\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 Ngeqslant n</tex>. Все все циклические сдвиги будут отсортированы. Всего шагов <tex>O(\log(N)n)</tex>, каждый шаг проводится за <tex>O(N n \log(n))</tex>, итоговая асимптотика <tex>O(N n \log^2(N)n)</tex>.

'''int[]'''suf_array('''string'''(s) suf <tex>\leftarrow \= {0, 1, \dots, |.. s|\.length}</tex> '''sort''' (suf, '''compare1''') <tex>c \leftarrow \= {</tex>s[0], s[1], ..., s[|s| .length - 1]<tex>\}</tex>

'''for''' <tex>l</tex> = 1 .. 2^('''toceil'''('''log2''' <tex>2^{\lceil \log_2(n)\rceil ) - 1}</tex> ) '''step''' <tex>l \leftarrow 2l</tex> '''do'''*= 2 '''sort''' (suf, '''compare2''') <tex>c'</tex>[suf[0]] <tex>\leftarrow</tex> = 0 '''for''' <tex>i</tex> = 1 '''to''' <tex>|.. s|.length -1</tex> '''do''' <tex>l_1 \leftarrow c</tex>[l1 = suf[<tex>i - 1</tex>]] <tex>r_1 \leftarrow c</tex>[r1 = suf[<tex>i - 1</tex>] + <tex>l</tex>] <tex>l_2 \leftarrow c</tex>[l2 = suf[<tex>i</tex>]] <tex>r_2 \leftarrow c</tex>[r2 = suf[<tex>i</tex>] + <tex>l</tex>] '''if''' (<tex>c</tex>[<tex>l_1</tex>l1] <tex>\neq</tex> <tex>c</tex>[<tex>l_2</tex>l2] '''or''' <tex>c</tex>[<tex>r_1</tex>r1] <tex>\neq</tex> <tex>c</tex>[<tex>r_2</tex>r2]) <tex>c'</tex>[suf[<tex>i</tex>]] = <tex>c'</tex>[suf[<tex>i - 1</tex> ]] + 1]]

<tex>c'</tex>[suf[<tex>i</tex>]] = <tex>c'</tex>[suf[<tex>i - 1</tex>]] <tex> c \leftarrow = c'</tex> '''retreturn''' suf

'''order'''compare1('''int'' (<tex>j_1</tex>' j1, '''int''' j2) '''if''' s[j1] <tex>j_2</tex>)s[j2] '''retreturn''' ''LT'' '''else if''' s[<tex>j_1</tex>j1] - == s[<tex>j_2</tex>j2] '''return''' ''EQ'' '''else''' '''return''' ''GT''

'''order'''compare2('''int''' (<tex>j_1</tex>j1, <tex>j_2</tex>'''int''' j2) '''if''' (<tex>c</tex>[<tex>j_1</tex>j1] <tex>\neq</tex> <tex>c</tex>_[<tex>j_2</tex>j2]) '''retreturn''' '''compare''' <tex>(c</tex>[<tex>j_1</tex>j1] - <tex>, c</tex>[<tex>j_2</tex>j2])

'''retreturn''' <tex>'''compare'''(c</tex>[<tex>j_1 j1 + l</tex>] - <tex>, c</tex>[<tex>j_2 j2 + l<]) ==См. также==* [[Суффиксный массив]]* [[Алгоритм цифровой сортировки суффиксов циклической строки]] ==Источники информации==[http://en.wikipedia.org/wiki/tex>Suffix_array#Construction_Algorithms Wikipedia — Suffix array construction algorithms] [[Категория:Алгоритмы и структуры данных]][[Категория:Суффиксный массив]]