14
правок
Изменения
→Пример: tex -> wikitable
{{Задача|definition == Постановка задачи == Дана циклическая строка <tex>s[0 .. n - 1]</tex>. Суффиксом циклической строки <tex>s</tex> называется строка <tex>s[i .. n - 1] + s[0 .. i - 1], i < n </tex> (будем называть такую строкую строку суффиксом под номером <tex>i</tex>). Требуется отсортировать все её суффиксы в порядке лексикографической сортировки.}}
== Решение ==
Рассматриваемый алгоритм состоит из <tex>\lceil\log n\rceil + 1</tex> итераций. На <tex>k</tex>-той итерации (<tex>k=0..\lceil\log n\rceil </tex>) сортируются циклические подстроки длины <tex>2^k</tex>. На последней, <tex>\lceil\log n\rceil</tex>-ой итерации, будут сортироваться подстроки длины <tex>2^{\lceil\log n\rceil} \ge geqslant n</tex>, что эквивалентно сортировке циклических сдвигов.
На каждой итерации алгоритм помимо будем хранить массив перестановки <tex>p[0..n-1]</tex> индексов циклических подстрок будет поддерживать для каждой циклической подстроки длиной , где <tex>2^kp[i]</tex>— номер суффикса, начинающейся занимающего позицию <tex>i</tex> в позиции текущей перестановке. Также будем хранить массив классов эквивалентности <tex>ic[0 .. n - 1]</tex>, номер класса эквивалентности где <tex>c[i]</tex>— класс эквивалентности, которому эта подстрока принадлежитпрефикс длины <tex>2^k</tex> суффикса под номером <tex>p[i]</tex>. В самом деле, среди подстрок могут быть одинаковые, и алгоритму понадобится информация об При этом. Кроме тогоесли префикс суффикса под номером <tex>p[i]</tex> лексикографически меньше префикса суффикса под номером <tex>p[j]</tex>, номера классов эквивалентности то <tex>c[i] < c[j]</tex> будем давать таким образом. Если же префиксы равны, чтобы они сохраняли то и информацию о порядке: если один их классы эквивалентности одинаковы. Так как мы вставили в строку символ <tex>\$</tex>, то к концу алгоритма каждый суффикс меньше другогобудет иметь уникальный класс эквивалентности, значит, то и номер класса он должен получить меньшиймы установим порядок суффиксов.
== Описание алгоритма ==
На нулевой итерации отсортируем циклические подстроки длины <tex>1</tex>, т.е. первые символы строк, и разделим их на классы эквивалентности (одинаковые символы должны быть отнесены к одному классу эквивалентности). При помощи [[Сортировка подсчетом|сортировки подсчетом]] построим массив <tex>p</tex>, содержащий номера суффиксов, отсортированных в лексикографическом порядке. По этому массиву построим массив классов эквивалентности <tex>c</tex>.
На <tex>k</tex>-ой итерации ом проходе имеем массивы <tex>p</tex> и <tex>c</tex>, вычисленные на предыдущей итерации. Приведем алгоритм, выполняющий <tex>k</tex>-ую итерацию ый проход за <tex>O(n)</tex>. Поскольку итераций всего <tex>O(\log n)</tex>, такой алгоритм имеет асимптотику <tex>O(n \log n)</tex>.
Заметим, что циклическая подстрока длины <tex>2^k</tex> состоит из двух подстрок длины <tex>2^{k-1}</tex>, которые мы можем сравнивать между собой за <tex>O(1)</tex>, используя информацию с предыдущей итерации — номера классов эквивалентности <tex>c</tex>. Таким образом, для подстроки длины <tex>2^k</tex>, начинающейся в позиции <tex>i</tex>, вся необходимая информация содержится в паре чисел <tex>\langle c[i], c[i + 2^{k-1}]\rangle </tex>.
[[Файл:Suff_array.png|350px|thumb|right|Циклическая подстрока длины <tex>2^k</tex> и порядок ее частей с прерыдущей итерации.]]
Отсортируем подстроки длины <tex>2^k</tex> по данным парам и запишем порядок в массив <tex>p</tex>. Воспользуемся здесь приёмом, на котором основана [[Цифровая сортировка| цифровая сортировка]]: отсортируем пары сначала по вторым элементам, а затем по первым (устойчивой сортировкой). Однако вторые элементы уже упорядочены — этот порядок задан в массиве от предыдущей итерации. Тогда, чтобы получить порядок пар по вторым элементам, надо от каждого элемента массива <tex>p</tex> отнять <tex>2^{k-1}</tex> (<tex>p</tex> даёт упорядочение подстрок длины <tex>2^{k-1}</tex>, и при переходе к строке вдвое большей длины эти подстроки становятся их вторыми половинками, поэтому от позиции второй половинки отнимается длина первой половинки).
==Пример==
<tex>
</tex>
{| class="wikitable" style="text-align: center;"
! colspan="3" | 0 фаза
! colspan="4" | 1 фаза
! colspan="4" | 2 фаза
! colspan="4" | 3 фаза
|-
| p
| s
| c
| p
|
|
| c
| p
|
|
| c
| p
|
|
| c
|-
| 7
| $
| 1
| 7
| $a
| 1,2
| 1
| 7
| $aba
| 1,5
| 1
| 7
| $abacaba
| 1,8
| 1
|-
| 0
| a
| 2
| 6
| a$
| 2,1
| 2
| 6
| a$ab
| 2,3
| 2
| 6
| a$abacab
| 2,5
| 2
|-
| 2
| a
| 2
| 0
| ab
| 2,3
| 3
| 4
| aba$
| 3,2
| 3
| 4
| aba$abac
| 3,4
| 3
|-
| 4
| a
| 2
| 4
| ab
| 2,3
| 3
| 0
| abac
| 3,4
| 4
| 0
| abacaba$
| 4,3
| 4
|-
| 6
| a
| 2
| 2
| ac
| 2,4
| 4
| 2
| acab
| 4,3
| 5
| 2
| acaba$ab
| 5,2
| 5
|-
| 1
| b
| 3
| 1
| ba
| 3,1
| 5
| 5
| ba$a
| 5,1
| 6
| 5
| ba$abaca
| 6,7
| 6
|-
| 5
| b
| 3
| 5
| ba
| 3,1
| 5
| 1
| baca
| 5,6
| 7
| 1
| bacaba$a
| 7,6
| 7
|-
| 3
| c
| 4
| 3
| ca
| 4,1
| 6
| 3
| caba
| 6,5
| 8
| 3
| caba$aba
| 8,1
| 8
|}
==Псевдокод==
<font color=darkgreen>/* преобразует масив count, так что
теперь он содержит позиции в массиве suffs с которых
необходимо вставлять подстроки, начинающиеся с соответствующих символов */</font> '''int[]'''calc_positions('''int[]'''(count)
count[0] = 0
'''for''' i = 2 .. count.length- 1
count[i] += count[i - 1]
'''return''' count
<font color=darkgreen>/* принимает строку, для которой требуется построить суффиксный массив возвращает суффиксный массив */</font> '''int[]'''suff_array('''string'''(str)
s += '$'
<font color=darkgreen>// нулевая итерация</font> count = '''int'''[max(ALPHABET<tex>|\Sigma|</tex>, str.length)]
'''fill'''(count, 0)
'''for''' ch '''in''' str
count[ch]++
count = '''calc_positions'''(count) <font color=darkgreen>// suffs будет хранить индексы начал отсортированных подстрок текущей длины</font>
suffs = '''int'''[str.length]
'''for''' ch '''in''' str
suffs[count[ch]++] = i;
classes = '''int'''[str.length]
classesN = 0
last_char = '$'
'''for''' suf '''in''' suffs
'''if''' s[suf] != <tex> \neq </tex> last_char
last_char = s[suf[i]]
classesN++
classes[suf] = classesN;
<font color=darkgreen>// нулевая итерация завершена // сортируем подстроки длиной 2 * cur_len = 2^k</font> curr_len cur_len = 1 '''while''' cur_len <= tex> \leqslant </tex> str.length <font color=darkgreen>// сортируем по второй половине подстроки</font>
sorted_by2 = '''int'''[str.length]
'''for''' i = 0 .. str.length- 1 sorted_by2[i] = (suffs[i] + str.length - cur_len) % '''mod''' str.length <font color=darkgreen>// сортируем по первой половине // сортировка устойчивая, значит получим целиком отсортированные подстроки</font>
'''fill'''(count, 0)
'''for''' by2 '''in''' sorted_by2
count[classes[by2]]++
count = '''calc_positions'''(count) '''for''' i = 0 .. str.length- 1
suffs[count[classes[sorted_by2[i]]]++] = sorted_by2[i]
new_classes = '''int'''[str.length]
classesN = 0
'''for''' i = 0 .. str.length- 1 mid1 = (suffs[i] + cur_len) % '''mod''' str.length mid2 = (suffs[i - 1] + cur_len) % '''mod''' str.length '''if''' classes[suffs[i]] != <tex> \neq </tex> classes[suffs[i-1]] '''or''' classes[mid1] != <tex> \neq </tex> classes[mid2] classesN++
new_classes[suffs[i]] = classesN
classes = new_classes
== Источники информации ==
* [http://e-maxx.ru/algo/suffix_array MAXimal :: algo :: Суффиксный массив]
* [http://www.geeksforgeeks.org/suffix-array-set-2-a-nlognlogn-algorithm Suffix Array | Set 2 (nLogn Algorithm)]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Суффиксный массив]]
[[Категория: Структуры данных]]
