Изменения

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

== Решение ==Рассматриваемый алгоритм состоит из примерно <tex>\log n</tex> фаз. На <tex>k-</tex>той фазе (<tex>k=0[[Файл:Suff_array..\lceil\log n\rceil </tex>) сортируются циклические подстроки png|350px|thumb|right|Циклическая подстрока длины <tex>2^k</tex>и порядок ее частей с прерыдущей итерации. На последней, <tex>\lceil\log n\rceil-</tex>ой фазе, будут сортироваться подстроки длины <tex>2^{\lceil\log n\rceil} \ge n</tex>, что эквивалентно сортировке циклических сдвигов.]]

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

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

Далее, пусть мы выполнили ==Пример==<tex>s = abacaba\$ \\i' = i + 2^{k-1-} \\</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</tex> и <tex>| | | c</tex> для неё). Научимся за <tex>O(n)</tex> выполнять следующую|-| 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, <tex>k6| 7|-</tex>ю| 3| c| 4| 3| ca| 4,1| 6| 3| caba| 6, фазу. Поскольку фаз всего <tex>O(\log n)</tex>5| 8| 3| caba$aba| 8, это даст нам требуемый алгоритм с временем <tex>O(n \log n)</tex>.1| 8|}

Заметим==Псевдокод== <font color=darkgreen>/* преобразует масив count, так что циклическая подстрока длины теперь он содержит позиции в массиве suffs с которых необходимо вставлять подстроки, начинающиеся с соответствующих символов */<tex/font> '''int[]''' calc_positions('''int[]''' count) count[0] = 0 '''for''' i = 2^k.. count.length - 1 count[i] += count[i - 1] '''return''' count <font color=darkgreen>/* принимает строку, для которой требуется построить суффиксный массив возвращает суффиксный массив */</texfont> состоит из двух подстрок длины '''int[]''' suff_array('''string''' str) s += '$' <texfont color=darkgreen>2^{k-1}// нулевая итерация</font> count = '''int'''[max(<tex>, которые мы можем сравнивать между собой за |\Sigma|</tex>O, str.length)] '''fill'''(count, 0) '''for''' ch '''in''' str count[ch]++ count = '''calc_positions'''(1count) <font color=darkgreen>// suffs будет хранить индексы начал отсортированных подстрок текущей длины</texfont>, используя информацию с предыдущей фазы — номера классов эквивалентности 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>c\neq </tex>. Таким образом, для подстроки длины last_char last_char = s[suf[i]] classesN++ classes[suf] = classesN <texfont 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>// сортируем по первой половине //tex>сортировка устойчивая, вся необходимая информация содержится в паре чисел значит получим целиком отсортированные подстроки<tex/font> '''fill'''(count, 0) '''for''' by2 '''in''' sorted_by2 count[classes[by2]]++ count = '''calc_positions'''(ccount) '''for''' i = 0 .. str.length - 1 suffs[count[classes[sorted_by2[i], c]]++] = sorted_by2[i] new_classes = '''int'''[str.length] classesN = 0 '''for''' i = 0 .. str.length - 1 mid1 = (suffs[i ] + 2^kcur_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

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