Изменения

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

Заметим, что циклическая [[Файл:Suff_array.png|350px|thumb|right|Циклическая подстрока длины <tex>2^k</tex> состоит из двух подстрок длины <tex>2^{k-1}</tex>, которые мы можем сравнивать между собой за <tex>O(1)</tex>, используя информацию и порядок ее частей с предыдущей фазы — номера классов эквивалентности <tex>c</tex>прерыдущей итерации. Таким образом, для подстроки длины <tex>2^k</tex>, начинающейся в позиции <tex>i</tex>, вся необходимая информация содержится в паре чисел <tex>(c[i], c[i + 2^{k-1}])</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: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

'''rotatereturn'''(count <font color=darkgreen>/* принимает строку, 1)для которой требуется построить суффиксный массив возвращает суффиксный массив */</font> ''сдвигаем массив на 1 вправо для удобства работы с индексами'' countint[0] = 0 //''теперь он содержит позиции в массиве suffs с которых '' //suff_array(''необходимо вставлять подстроки, начинающиеся с соответствующих символов'' '''suff_arraystring'''(string &sstr) s += '#$' <font color=darkgreen>//''На нулевом этапе сортируем подстроки длинной 1''нулевая итерация</font> '''vector''' count(max(= '''int'''[max(alpha_size)<tex>|\Sigma|</tex>, sstr.length())) //''count -- массив для сортировки подсчетом'']

'''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] + s_len str.length - cur_len ) '''elsemod'''str.length sorted_by2[i] <font color= suffs[i] - cur_len darkgreen>//''теперь сортируем по первой половине'' //''сортировка стабильнаустойчивая, значит получим целиком отсортированные подстроки''</font>

'''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

//''Подстроки текущей длины отсортированы'' //new_classes = ''перещитаем классы эквивалентности'' int'''vector''' new_classes(s[str.length()) new_classes[suffs[0]] = 0 classes_count classesN = 0 '''for''' ('''int''' i = 0 .. str.length - 1; i < new_classes.size(); ++i) '''int''' mid1 = (suffs[i] + cur_len) % suffs.size() '''intmod''' str.length mid2 = (suffs[i-1] + cur_len) % suffs'''mod''' str.size()length '''if''' (classes[suffs[i]] != <tex> \neq </tex> classes[suffs[i-1]] || '''or''' classes[mid1] != <tex> \neq </tex> classes[mid2]) classesN++classes_count new_classes[suffs[i]] = classes_countclassesN '''copy'''(classes = new_classes, classes)//''сохраняем новые классы в classes'' cur_len *= 2