497
правок
Изменения
Нет описания правки
= Описание алгоритма =
Основная идея алгоритма, заключается в том что мы уменьшаем размер исходной строки. Для этого мы разбиваем символы сходной строки на пару и пронумеровываем их, а из полученных номеров составляем новую строку, которая уже в <tex>2 </tex> раза короче.
Мы опишем алгоритм Фарача в виде пяти выполняемых шагов. Используем в качестве примера строку <tex>s = 121112212221</tex>, определенную на алфавите <tex>А \Sigma = \{1, 2} </tex> (в этом примере <tex>N = 12</tex>).
=== Шаг 1: суффиксное дерево для сжатой строки===
* Удаляются копии: <tex>11 12 21 22</tex>.
* Парам даются номера (условно, в массиве они и так есть): <tex>11-(0), 12-(1), 21-(2), 22-(3)</tex>
* Создаётся новая строка из номеров пар: <tex>1 0 1 2 3 2</tex>
* Из полученной строки создаётся суффикcное дерево:
[[Файл:tree101232.png|300px|thumb|right|суфдерево для сжатой строки]]
Из дерева сжатой строки получаем частичное (чётное) дерево исходной строки. Частичное потому в нём будут только половина суффиксов, т.е. тех которые стоят в чётных позициях. :
[[Файл:Tree101232even-pre.png|300px|thumb|left|Очевидно, что для этого достаточно умножить все расстояния в дереве на 2]]
[[Файл:Tree101232even.png|300px|thumb|center|Корректируются все развилки дерева (так как они могут совпадать в первых символах)]]
