Изменения

{{В разработке}}Задача|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>p[i]</tex> — номер суффикса, занимающего позицию <tex>i</tex> с длиной в текущей перестановке. Также будем хранить массив классов эквивалентности <tex>2^kc[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>p</tex> и сравнением символов, строится построим массив классов эквивалентности <tex>c</tex>.

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

Осталось только пересчитать номера классов эквивалентности <tex>c</tex>, просто пройдя по полученной новой перестановке <tex>p</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,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(<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> 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 cur_len *= 2 '''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)] [[Категория: Алгоритмы и структуры данных]][[Категория: Суффиксный массив]][[Категория: Структуры данных]]