1632
правки
Изменения
м
Пусть мы выполнили На <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>.
Это даёт нам весьма простое решение[[Файл: отсортировать подстроки 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> с помощью сортировки подсчётом, и при переходе к строке вдвое большей длины эти подстроки становятся их вторыми половинками, поэтому от позиции второй половинки отнимается длина первой половинки).
s = abacaba$
\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}
rollbackEdits.php mass rollback
{{Задача|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>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>.
Чтобы произвести устойчивую сортировку по первым элементам пар, воспользуемся сортировкой подсчетом, имеющую асимптотику <tex>O(n)</tex>. Осталось только пересчитать номера классов эквивалентности <tex>c</tex>, просто пройдя по полученной новой перестановке <tex>p</tex> и сравнивая соседние элементы (опять же, сравнивая как пары двух чисел).
==Пример==
<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
|
|
| 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> '''calc_positionsint[]'''calc_positions('''vectorint[]''' &count) //''преобразуем масив count''[0] = 0 '''for''' ('''int''' i = 1; i < 2 .. count.size(); ++i)length - 1 count[i] += count[i - 1]; '''rotatereturn'''(count <font color=darkgreen>/* принимает строку, 1);для которой требуется построить суффиксный массив возвращает суффиксный массив */</font> ''сдвигаем массив на 1 вправо для удобства работы с индексами'' countint[0] = 0; //''теперь он содержит позиции в массиве suffs с которых 'suff_array(' //''необходимо вставлять подстроки, начинающиеся с соответствующих символов'' '''suff_arraystring'''(string &sstr) s += '$'; int alpha_size = 255; <font color=darkgreen>//''На нулевом этапе сортируем подстроки длиной 1''нулевая итерация</font> count = '''vectorint''' count([max(alpha_size<tex>|\Sigma|</tex>, sstr.length())); //''count -- массив для сортировки подсчетом''] '''fill'''(count, 0); '''for''' (ch '''intin''' i = 0; i < s.length(); ++i)str ++count[ord(s[ich])];++ 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; //classes = ''подстроки длиной 1 отсортированы'int' //''разобьем их на классы эквивалентности'' '''vector''' 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_count;classesN <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] + sstr.length() - cur_len; ) '''elsemod'''str.length sorted_by2[i] <font color= suffs[i] - cur_len; darkgreen>//''теперь сортируем по первой половине'' //''сортировка устойчивая, значит получим целиком отсортированные подстроки''</font> '''fill'''(count, 0); '''for''' (by2 '''intin''' i = 0; i < sorted_by2.size() ++i) ++count[classes[sorted_by2[iby2]]];++ count = '''calc_positions'''(count); '''for''' ('''int''' i = 0; i < s.. str.length(); ++i)- 1 suffs[count[classes[sorted_by2[i]]]++] = sorted_by2[i]; //''Подстроки текущей длины отсортированы'' //''переcчитаем классы эквивалентности'' new_classes = '''vectorint''' 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_count;classesN //''сохраняем новые классы в classes''= new_classes '''copy'''(new_classes, classes);cur_len *= 2 '''return''' suffs;
== Источники См. также ==
* [[Суффиксный массив]]
* [http://e-maxx.ru/algo/suffix_array e-maxx.ru[Построение суффиксного массива с помощью стандартных методов сортировки]]
== Источники информации ==
* [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)]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Суффиксный массив]]
[[Категория: Структуры данных]]