497
правок
Изменения
→Описание алгоритма
Основная идея алгоритма, заключается в том что мы уменьшаем размер исходной строки. Для этого мы разбиваем символы сходной строки на пару и пронумеровываем их, а из полученных номеров составляем новую строку, которая уже в <tex>2</tex> раза короче.
Мы опишем алгоритм Фарача в виде пяти выполняемых шагов. Используем в качестве примера строку <tex>s = 121112212221</tex>, определенную на алфавите <tex>\Sigma = \{1, 2\} </tex> (в этом примере <tex>N = 12</tex>).
=== Шаг 1: суффиксное дерево для сжатой строки===
* Строка <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>.
