Изменения

{{В разработкеЗадача|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} \geqslant n</tex>, что эквивалентно сортировке циклических сдвигов. На каждой итерации будем хранить массив перестановки <tex>p[0 .. n - 1]</tex>, где <tex>p[i]</tex> — номер суффикса, занимающего позицию <tex>i</tex> в текущей перестановке. Также будем хранить массив классов эквивалентности <tex>c[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>s1</tex>, т. Требуется отсортировать все её суффиксые. Поскольку мы сортируем циклические сдвигипервые символы строк, то и подстроки мы будем рассматривать циклические: под подстрокой <tex>sразделим их на классы эквивалентности (одинаковые символы должны быть отнесены к одному классу эквивалентности). При помощи [[i..jСортировка подсчетом|сортировки подсчетом]]</tex>, когда построим массив <tex>i > jp</tex>, понимается подстрока содержащий номера суффиксов, отсортированных в лексикографическом порядке. По этому массиву построим массив классов эквивалентности <tex>s[i..n-1] + s[0..j]c</tex>. Кроме того, предварительно все индексы берутся по модулю длины строки.

== Решение ==Рассматриваемый алгоритм состоит из примерно На <tex>k</tex>-ом проходе имеем массивы <tex>p</tex> и <tex>\log nc</tex> фаз, вычисленные на предыдущей итерации. На Приведем алгоритм, выполняющий <tex>k</tex>-ый проход за </tex>той фазе O(n)</tex>k=0..Поскольку итераций всего <tex>O(\lceillog n)</tex>, такой алгоритм имеет асимптотику <tex>O(n \log n\rceil )</tex>. Заметим, что циклическая подстрока длины <tex>2^k</tex> состоит из двух подстрок длины <tex>2^{k-1}</tex>, которые мы можем сравнивать между собой за <tex>O(1) сортируются циклические </tex>, используя информацию с предыдущей итерации — номера классов эквивалентности <tex>c</tex>. Таким образом, для подстроки длины <tex>2^k</tex>. На последней, начинающейся в позиции <tex>\lceil\log n\rceil-i</tex>ой фазе, будут сортироваться подстроки длины вся необходимая информация содержится в паре чисел <tex>\langle c[i], c[i + 2^{\lceil\log n\rceilk-1} ]\ge nrangle </tex>, что эквивалентно сортировке циклических сдвигов.

На каждой фазе алгоритм помимо перестановки <tex>p[0[Файл:Suff_array..n-1]</tex> индексов циклических подстрок будет поддерживать для каждой циклической подстроки, начинающейся в позиции <tex>i</tex> с длиной png|350px|thumb|right|Циклическая подстрока длины <tex>2^k</tex>, номер класса эквивалентности <tex>c[i]</tex>, которому эта подстрока принадлежит. В самом деле, среди подстрок могут быть одинаковые, и алгоритму понадобится информация об этомпорядок ее частей с прерыдущей итерации. Кроме того, номера классов эквивалентности <tex>c[i]</tex>, будем давать таким образом, чтобы они сохраняли и информацию о порядке: если один суффикс меньше другого, то и номер класса он должен получить меньший.]

На нулевой фазе мы должны отсортировать циклические подстроки длины <tex>1</tex>, т.е. отдельные символы строкиЧтобы произвести устойчивую сортировку по первым элементам пар, и разделить их на классы эквивалентности (одинаковые символы должны быть отнесены к одному классу эквивалентности). Это можно сделать воспользуемся сортировкой подсчётом. Для каждого символа посчитаемподсчетом, сколько раз он встретился. Потом по этой информации восстановим массив имеющую асимптотику <tex>p</tex>. После этого, проходом по массиву <tex>p</tex> и сравнением символов, строится массив <tex>cO(n)</tex>.

Далее, пусть мы выполнили Осталось пересчитать номера классов эквивалентности <tex>k-1-c</tex>ю фазу (т.е. вычислили значения массивов , пройдя по новой перестановке <tex>p</tex> и <tex>c</tex> для неё). Научимся за <tex>O(n)</tex> выполнять следующую, <tex>k-</tex>ю, фазу. Поскольку фаз всего <tex>O(\log n)</tex>, это даст нам требуемый алгоритм с временем <tex>Oсравнивая соседние элементы (n \log nкак пары двух чисел)</tex>.

Заметим, что циклическая подстрока длины <tex>2^k</tex> состоит из двух подстрок длины ==Пример==<tex>s = abacaba\$ \\i' = i + 2^{k-1}\\</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, которые мы можем сравнивать между собой за <tex>O(1)</tex>| 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, используя информацию с предыдущей фазы — номера классов эквивалентности <tex>c</tex>. Таким образом3| 5| 2| acaba$ab| 5, для подстроки длины <tex>2^k</tex>| 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, начинающейся в позиции <tex>i</tex>6| 7| 1| bacaba$a| 7, вся необходимая информация содержится в паре чисел <tex>(6| 7|-| 3| c[i]| 4| 3| ca| 4,1| 6| 3| caba| 6,5| 8| 3| caba$aba| 8, c[i + 2^k])</tex>.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(<tex>2^k|\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> cur_len = 1 '''while''' cur_len <tex>p\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>n \log nneq </tex>, нас не устроит — это даст алгоритм построения суффиксного массива с временем classes[suffs[i-1]] '''or''' classes[mid1] <tex>n \log^2 nneq </tex>.classes[mid2] classesN++ new_classes[suffs[i]] = classesN classes = new_classes cur_len *= 2 '''return''' suffs

Воспользуемся здесь приёмом, на котором основана цифровая сортировка: чтобы отсортировать пары, отсортируем их сначала по вторым элементам, а затем — по первым элементам (обязательно стабильной сортировкой)== См. Однако отдельно вторые элементы уже упорядочены — этот порядок задан в массиве от предыдущей фазы. Тогда, чтобы упорядочить пары по вторым элементам, надо просто от каждого элемента также ==* [[Суффиксный массив]]* [[Построение суффиксного массива <tex>p</tex> отнять <tex>2^{k-1}<tex> — это даст нам порядок с помощью стандартных методов сортировки пар по вторым элементам (<tex>p</tex> даёт упорядочение подстрок длины <tex>2^{k-1}</tex>, и при переходе к строке вдвое большей длины эти подстроки становятся их вторыми половинками, поэтому от позиции второй половинки отнимается длина первой половинки).]]

Таким образом, мы производим сортировку по вторым элементам пар== Источники информации ==* [http://e-maxx. Теперь надо произвести стабильную сортировку по первым элементам пар, её уже можно выполнить за <tex>Oru/algo/suffix_array MAXimal :: algo :: Суффиксный массив]* [http://www.geeksforgeeks.org/suffix-array-set-2-a-nlognlogn-algorithm Suffix Array | Set 2 (nnLogn Algorithm)</tex> с помощью сортировки подсчётом.]

Осталось только пересчитать номера классов эквивалентности <tex>c</tex>, просто пройдя по полученной новой перестановке <tex>p</tex> [[Категория: Алгоритмы и сравнивая соседние элементы (опять же, сравнивая как пары двух чисел).структуры данных]][[Категория: Суффиксный массив]][[Категория: Структуры данных]]