Изменения

{{Задача|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} \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>p</tex> и сравнением символов строится построим массив классов эквивалентности <tex>c</tex>.

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

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

Чтобы произвести устойчивую сортировку по первым элементам пар, воспользуемся сортировкой подсчетом, имеющую асимптотику <tex>O(n)</tex>. Осталось только пересчитать номера классов эквивалентности <tex>c</tex>, просто пройдя по полученной новой перестановке <tex>p</tex> и сравнивая соседние элементы (опять же, сравнивая как пары двух чисел).

\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|}\hline\multicolumn{3}{|l|}{0 iteration} & \multicolumn{4}{l|}{1 iteration} & \multicolumn{4}{l|}{2 iteration} & \multicolumn{4}{l|}{3 iteration} \\ \hlinep & & c & p & & & c & p & & & c & p & & & c \\ \hline7 & \$ & 1 & 7 & \$a & \textless1, 2\textgreater & 1 & 7 & \$aba & \textless1, 5\textgreater & 1 & 7 & \$s = abacaba & \textless1, 8\textgreater & 1 \\ \hline0 & a & 2 & 6 & a\$ & \textless2, 1\textgreater & 2 & 6 & a\$ab & \textless2, 3\textgreater & 2 & 6 & a\$abacab & \textless2, 5\textgreater & 2 \\ \hlinei' = i + 2 & a & 2 & 0 & ab & \textless2, 3\textgreater & 3 & 4 & aba\$ & \textless3, 2\textgreater & 3 & 4 & aba\$abac & \textless3, 4\textgreater & 3 \\ \hline4 & a & 2 & 4 & ab & \textless2, 3\textgreater & 3 & 0 & abac & \textless3, 4\textgreater & 4 & 0 & abacaba\$ & \textless4, 3\textgreater & 4 \\ \hline6 & a & 2 & 2 & ac & \textless2, 4\textgreater & 4 & 2 & acab & \textless4, 3\textgreater & 5 & 2 & acaba\$ab & \textless5, 2\textgreater & 5 \\ \hline^{k-1 & b & 3 & 1 & ba & \textless3, 1\textgreater & 5 & 5 & ba\$a & \textless5, 1\textgreater & 6 & 5 & ba\$abaca & \textless6, 7} \textgreater & 6 \\ \hline5 & b & 3 & 5 & ba & \textless3, 1\textgreater & 5 & 1 & baca & \textless5, 6\textgreater & 7 & 1 & bacaba\$a & \textless7, 6\textgreater & 7 \\ \hline3 & c & 4 & 3 & ca & \textless4, 1\textgreater & 6 & 3 & caba & \textless6,5\textgreater & 8 & 3 & caba\$aba & \textless8, 1\textgreater & 8 \\ \hline\end{tabular}

<font color=darkgreen>/* преобразует масив count, так что

необходимо вставлять подстроки, начинающиеся с соответствующих символов */</font> '''int[]'''calc_positions('''int[]'''(count)

'''for''' i = 2 .. count.length- 1

<font color=darkgreen>/* принимает строку, для которой требуется построить суффиксный массив возвращает суффиксный массив */</font> '''int[]'''suff_array('''string'''(str)

<font color=darkgreen>// нулевая итерация</font> count = '''int'''[max(ALPHABET<tex>|\Sigma|</tex>, str.length)]

count = '''calc_positions'''(count) <font color=darkgreen>// suffs будет хранить индексы начал отсортированных подстрок текущей длины</font>

suffs[count[ch]++] = i;

'''if''' s[suf] != <tex> \neq </tex> last_char

classes[suf] = classesN;

<font color=darkgreen>// нулевая итерация завершена // сортируем подстроки длиной 2 * cur_len = 2^k</font> curr_len cur_len = 1 '''while''' cur_len <= tex> \leqslant </tex> str.length <font color=darkgreen>// сортируем по второй половине подстроки</font>

'''for''' i = 0 .. str.length- 1 '''if''' suffs[i] < cur_len sorted_by2[i] = (suffs[i] + str.length() - cur_len ) '''elsemod'''str.length sorted_by2[i] <font color= suffs[i] - cur_len darkgreen>// сортируем по первой половине // сортировка устойчивая, значит получим целиком отсортированные подстроки</font>

count = '''calc_positions'''(count) '''for''' i = 0 .. str.length- 1

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

== Источники См. также ==

* [http://e-maxx.ru/algo/suffix_array e-maxx.ru[Построение суффиксного массива с помощью стандартных методов сортировки]]