14
правок
Изменения
→Пример: tex -> wikitable
{{Задача|definition == Постановка задачи == Дана циклическая строка <tex>s</tex>. Требуется отсортировать все её суффиксы. Поскольку строка циклическая, то и подстроки мы будем рассматривать циклические: под подстрокой <tex>s[i0 ..jn - 1]</tex>, когда . Суффиксом циклической строки <tex>i > js</tex>, понимается подстрока называется строка <tex>s[i..n-1] + s[0..ji - 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>pc</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>c</tex>, просто пройдя по полученной новой перестановке <tex>p</tex> и сравнивая соседние элементы (опять же, сравнивая как пары двух чисел).
==Пример==
<tex>s = abacaba\$\\i' = i + 2^{k-1} \\</tex>[[Файл{| class="wikitable" style="text-align:Suffixcenter;"! 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|-array2.png]]| 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> '''calc_positionsint[]'''calc_positions('''vectorint[]''' &count) //''преобразуем масив count''[0] = 0 '''for''' ('''int''' i = 1; i < 2 .. count.size(); ++i)length - 1
count[i] += count[i - 1]
'''rotatereturn'''(count <font color=darkgreen>/* принимает строку, 1)для которой требуется построить суффиксный массив возвращает суффиксный массив */</font> ''сдвигаем массив на 1 вправо для удобства работы с индексами'' countint[0] = 0 //''теперь он содержит позиции в массиве suffs с которых 'suff_array(' //''необходимо вставлять подстроки, начинающиеся с соответствующих символов'' string'''suff_array'''(string &sstr) s += '#$' int alpha_size = 255 <font color=darkgreen>//''На нулевом этапе сортируем подстроки длинной 1''нулевая итерация</font> count = '''vectorint''' count([max(alpha_size<tex>|\Sigma|</tex>, sstr.length())) //''count -- массив для сортировки подсчетом'']
'''fill'''(count, 0)
'''for''' (ch '''intin''' i = 0; i < s.length(); ++i)str ++count[s[i]ch]++ count = '''calc_positions'''(count) '''vector''' suffs(s.length()) <font color=darkgreen>//''suffs будет хранить индексы начал отсортированных подстрок текущей длины</font> suffs = '''int'''[str.length] '''for''' (ch '''intin''' i = 0; i < s.length(); ++i)str suffs[count[ord(s[i])ch]++] = i //''подстроки длинной 1 отсортированы'' //''разобьем их на классы эквивалентности'' '''vector'''<classes = '''int'''> classes(s[str.length())] '''int''' classes_count classesN = 0 '''char''' last_char = '#$' '''for''' (suf '''intin''' i = 0; i < suffs.size(); ++i) '''if''' s[suffs[isuf]] != <tex> \neq </tex> last_char last_char = s[suffssuf[i]] classesN++classes_count classes[suffs[i]suf] = classes_countclassesN <font color=darkgreen>//''нулевой этап завершен''нулевая итерация завершена //''на следующих этапах сортируем подстроки длиной 2 * cur_len = 2^k''</font> cur_len = 1 '''for''' ('''intwhile''' cur_len = 1; cur_len <= stex> \leqslant </tex> str.length(); cur_len *= 2) <font color=darkgreen>//''сортируем по второй половине подстроки''</font> sorted_by2 = '''vectorint''' sorted_by2(s[str.length())] '''for''' ('''int''' i = 0; i < suffs.size(); ++i). str.length - 1 '''if''' suffs[i] < cur_len sorted_by2[i] = (suffs[i] + sstr.length() - cur_len ) '''elsemod'''str.length sorted_by2[i] <font color= suffs[i] - cur_len darkgreen>//''теперь сортируем по первой половине'' //''сортировка стабильнаустойчивая, значит получим целиком отсортированные подстроки''</font>
'''fill'''(count, 0)
'''for''' (by2 '''intin''' i = 0; i < sorted_by2.size() ++i) ++count[classes[sorted_by2[i]by2]]++ count = '''calc_positions'''(count) '''for''' ('''int''' i = 0; i < s.. str.length(); ++i)- 1
suffs[count[classes[sorted_by2[i]]]++] = sorted_by2[i]
'''return''' suffs
== См. также ==
* [[Суффиксный массив]]
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
== Источники информации ==
* [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)]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Суффиксный массив]]
[[Категория: Структуры данных]]