97
правок
Изменения
langle & rangle вместо less & greater
На <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</tex> состоит из двух подстрок длины <tex>2^{k-1}</tex>, которые мы можем сравнивать между собой за <tex>O(1)</tex>, используя информацию с предыдущей итерации — номера классов эквивалентности <tex>c</tex>. Таким образом, для подстроки длины <tex>2^k</tex>, начинающейся в позиции <tex>i</tex>, вся необходимая информация содержится в паре чисел <tex>\textless langle c[i], c[i + 2^{k-1}]\textgreater rangle </tex>.
Отсортируем подстроки длины <tex>2^k</tex> по данным парам и запишем порядок в массив <tex>p</tex>. Воспользуемся здесь приёмом, на котором основана [[Цифровая сортировка| цифровая сортировка]]: отсортируем пары сначала по вторым элементам, а затем по первым (устойчивой сортировкой). Однако вторые элементы уже упорядочены — этот порядок задан в массиве от предыдущей итерации. Тогда, чтобы получить порядок пар по вторым элементам, надо от каждого элемента массива <tex>p</tex> отнять <tex>2^{k-1}</tex> (<tex>p</tex> даёт упорядочение подстрок длины <tex>2^{k-1}</tex>, и при переходе к строке вдвое большей длины эти подстроки становятся их вторыми половинками, поэтому от позиции второй половинки отнимается длина первой половинки).
\multicolumn{3}{|l|}{0 iteration} & \multicolumn{4}{l|}{1 iteration} & \multicolumn{4}{l|}{2 iteration} & \multicolumn{4}{l|}{3 iteration} \\ \hline
p & & c & p & & & c & p & & & c & p & & & c \\ \hline
7 & \$ & 1 & 7 & \$a & $\textless1langle1, 2\textgreater rangle$ & 1 & 7 & \$aba & $\textless1langle1, 5\textgreater rangle$ & 1 & 7 & \$abacaba & $\textless1langle1, 8\textgreater rangle$ & 1 \\ \hline0 & a & 2 & 6 & a\$ & $\textless2langle2, 1\textgreater rangle$ & 2 & 6 & a\$ab & $\textless2langle2, 3\textgreater rangle$ & 2 & 6 & a\$abacab & $\textless2langle2, 5\textgreater rangle$ & 2 \\ \hline2 & a & 2 & 0 & ab & $\textless2langle2, 3\textgreater rangle$ & 3 & 4 & aba\$ & $\textless3langle3, 2\textgreater rangle$ & 3 & 4 & aba\$abac & $\textless3langle3, 4\textgreater rangle$ & 3 \\ \hline4 & a & 2 & 4 & ab & $\textless2langle2, 3\textgreater rangle$ & 3 & 0 & abac & $\textless3langle3, 4\textgreater rangle$ & 4 & 0 & abacaba\$ & $\textless4langle4, 3\textgreater rangle$ & 4 \\ \hline6 & a & 2 & 2 & ac & $\textless2langle2, 4\textgreater rangle$ & 4 & 2 & acab & $\textless4langle4, 3\textgreater rangle$ & 5 & 2 & acaba\$ab & $\textless5langle5, 2\textgreater rangle$ & 5 \\ \hline1 & b & 3 & 1 & ba & $\textless3langle3, 1\textgreater rangle$ & 5 & 5 & ba\$a & $\textless5langle5, 1\textgreater rangle$ & 6 & 5 & ba\$abaca & $\textless6langle6, 7\textgreater rangle$ & 6 \\ \hline5 & b & 3 & 5 & ba & $\textless3langle3, 1\textgreater rangle$ & 5 & 1 & baca & $\textless5langle5, 6\textgreater rangle$ & 7 & 1 & bacaba\$a & $\textless7langle7, 6\textgreater rangle$ & 7 \\ \hline3 & c & 4 & 3 & ca & $\textless4langle4, 1\textgreater rangle$ & 6 & 3 & caba & $\textless6langle6, 5\textgreater rangle$ & 8 & 3 & caba\$aba & $\textless8langle8, 1\textgreater rangle$ & 8 \\ \hline
\end{tabular}
</tex>
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
== Источники информации ==
* [http://e-maxx.ru/algo/suffix_array MAXimal :: algo :: Суффиксный массив]
