Изменения

Согласно [[Суффиксный массив|определению]] суффиксного массива, для его построения достаточно отсортировать все суффиксы строки. Заменим сортировку суффиксов строки <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>.

== Алгоритм за O(N log^2(N)) (хэши) = Псевдокод ===

Данный алгоритм является некоторым улучшением предыдущего '''int[]''' sufArray('''string''' s) suf = {0, 1 . Основная цель - сократить оценку времени сравнения двух циклических сдвигов до <tex>O. s.length} '''sort'''(logsuf, compare) '''return''' suf '''order''' compare(n'''int''' j1, '''int''' j2) '''for''' i = 0 .. s.length '''if''' (s[(j1 + i)</tex'''mod''' s.length] >, тогда мы по аналогии с предыдущим алгоритмом получим оценку <tex>Os[(j2 + i) '''mod''' s.length]) '''return''' ''GT'' '''if''' (N log^2s[(N)j1 + i)</tex>'''mod''' s. Для этого вычислим хэши всех префиксов строки <tex>\alpha\$length] </tex> за <tex>Os[(Nj2 + i)</tex>'''mod''' s. Теперь у нас есть возможность проверять на равенство любые две подстроки (правда с определенной вероятностью мы можем получить неверный ответ на запросlength]). '''return''' ''LT'' '''return''' ''EQ''

Далее пусть нам необходимо сравнить два циклических сдвига <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(s[i_1..i_1,-1]</tex> и <tex>s[i_2..i_2) = N-1]</tex>, то строки равны. Если же Найдем сначала их наибольший общий префикс (<tex>lcp(i_1,i_2) < N</tex>), для этого будем использовать двоичный поиск по длине совпадающего префикса, то символы <tex>s[i_1 + lcp]</tex> а проверку осуществлять с помощью посчитанных хешей префиксов. Поскольку циклический сдвиг состоит из суффикса и префикса <tex>s[i_2suf +lcp]pref</tex> точно различаютсяисходной строки, их сравнение позволяет сделать вывод, какой из циклических сдвигов меньше в лексикографическом порядке. И так двоичный поиск работает за то с помощью двух хешей префиксов исходной строки можно найти хеш <tex>O(log(N))suf</tex> остальные операции требуют константного времени, получаем оценку времени, необходимого на сравнение двух циклических сдвигов или префикса <tex>O(log(N))suf</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(N \log^2(Nn)) (префиксы </tex>, остальные операции требуют константного времени, следовательно, время, необходимое на сравнение двух циклических сдвигов, оценивается как <tex>O(\log n) ==</tex>.

В начале легко можно отсортировать за <tex>O '''int[]''' sufArray('''string''' s) suf = {0, 1 .. s.length} '''sort'''(N logsuf, compare) '''return''' suf '''order''' compare(N'''int''' j1, '''int''' j2) same = '''lcp'''(j1, j2) '''if''' s[j1 + same] </tex> префиксы длины <texs[j2 + same] '''return''' ''LT'' '''else if''' s[j1 + same] == s2[j2 + same] '''return''' ''EQ'' '''else''' '''return''' ''GT'' '''int''' lcp(j1, j2) l = -1 r = s.length + 1 '''while''' r - l >1< m = (r + l) /tex>, т2 '''if''' hash[j1 .е. символыj1 + m] == hash[j2 . А номера классов поставить в соответствии с порядковым номером символа в алфавите.j2 + m] l = m '''else''' r = m '''return''' l

Рассмотрим теперь переход от префиксов длины <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(Nlog(n))</tex>. Вычислить новые <tex>c[i]</tex> можно легко просто пробежавшись в лексикографическом порядке по префиксам, и увеличивая значение соответствующего класса на <tex>1</tex> если текущий префикс не совпадает с предыдущим (сравнивать с помощью старых <tex>c[i], c[i+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> среди этих префиксов. Причем классы эквивалентности должны быть пронумерованы в лексикографическом порядке соответствующих представителей. Сначала легко можно отсортировать за <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 Ngeqslant n</tex>. Все все циклические сдвиги будут отсортированы. Всего шагов <tex>O(\log(N)n)</tex>, каждый шаг проводится за <tex>O(N n \log(n))</tex>, итоговая асимптотика <tex>O(N n \log^2n)</tex>. Схожая идея используется и в [[Алгоритм цифровой сортировки суффиксов циклической строки|алгоритме цифровой сортировки суффиксов циклической строки]], который имеет лучшую асимптотику.=== Псевдокод === '''int[]''' suf_array('''string''' s) suf = {0, 1 .. s.length} '''sort'''(suf, compare1) c = {s[0], s[1] .. s[s.length - 1]} '''for''' l = 1 .. 2^('''ceil'''('''log2'''(n)) - 1) '''step''' l *= 2 '''sort'''(suf, compare2) c'[suf[0]] = 0 '''for''' i = 1 .. s.length - 1 l1 = suf[i - 1] r1 = suf[i - 1] + l l2 = suf[i] r2 = suf[i] + l '''if''' c[l1] <tex>\neq</tex> c[l2] '''or''' c[r1] <tex>\neq</tex> c[r2] c'[suf[i]] = c'[suf[i - 1]] + 1 '''else''' c'[suf[i]] = c'[suf[i - 1]] c = c' '''return''' suf '''order''' compare1(N'''int''' j1, '''int''' j2) '''if''' s[j1] < s[j2] '''return''' ''LT'' '''else if''' s[j1] == s[j2] '''return''' ''EQ'' '''else''' '''return''' ''GT'' '''order''' compare2('''int''' j1, '''int''' j2) '''if''' c[j1] <tex>\neq</tex>c[j2] '''return''' '''compare'''(c[j1], c[j2]) '''else''' '''return''' '''compare'''(c[j1 + l], c[j2 + l]) ==См. также==* [[Суффиксный массив]]* [[Алгоритм цифровой сортировки суффиксов циклической строки]] ==Источники информации==[http://en.wikipedia.org/wiki/Suffix_array#Construction_Algorithms Wikipedia — Suffix array construction algorithms] [[Категория:Алгоритмы и структуры данных]][[Категория:Суффиксный массив]]