497
правок
Изменения
→шаг 0: суффиксное дерево для сжатой строки
Мы опишем алгоритм Фарача в виде пяти выполняемых шагов. Используем в качестве примера строку <tex>s = 121112212221</tex>, определенную на алфавите <tex>А = {1, 2} </tex> (в этом примере N = 12).
== шаг 0: суффиксное дерево для сжатой строки==
* Строка <tex>s</tex> разбивается на пары: <tex> 12 11 12 21 22 21 </tex>
* Пары сортирутся поразрядной сортировкой: <tex>11 12 12 21 21 22 </tex>.
* Удаляются копии: <tex>11 12 21 22</tex>.
* Парам даются номера (условно, в массиве они и так есть): <tex>11-(0), 12-(1), 21-(2), 22-(3)</tex>
* Создаётся новая строка из номеров пар: 1 0 1 2 3 2
* Из полученной строки создаётся суффикcное дерево:
== шаг 1: построение нечетного дерева ==
