Изменения

Перейти к: навигация, поиск

Алгоритм Фараха

29 байт добавлено, 18:52, 16 июня 2015
Нет описания правки
Для того чтобы узнать общее начало двойной дуги, нужно взять одну чётную и одну нечётную вершину на дереве, для которых родителем является конец нашей двойной дуги. Например, на рисунке выше двойная дуга <tex>(1)</tex> (конец помечен зелёным) является общим родителем для вершин <tex>3</tex> и <tex>6</tex>. Чтобы узнать, на каком расстоянии будет расслаиваться двойная дуга, надо увеличить номера вершин на единицу и найти их родителя. Он будет находиться на единицу ближе к корню (и путь у вершин будет одинаковой строкой, не считая размера). Родитель вершин <tex>4</tex> и <tex>7</tex> помечен жёлтым, он находится на расстоянии <tex>1</tex> от корня, следовательно, дуга <tex>(1)</tex> должна расслаиваться в двух символах от корня, то есть обе дуги совпадают и их просто надо слить.
 
[[Файл:Treestep5_2.jpg|thumb|650px|итоговое дерево]]
Разберём дуги по порядку:
# конец является родителем <tex>1</tex>, <tex>4</tex>. Расслаивается на втором символе.
# конец является родителем <tex>0</tex>, <tex>3</tex>. Дугу <tex>(5)</tex> можно обрабатывать только после дуги <tex>(4)</tex>, так как от неё будет зависеть глубина расслоения.
 
 
[[Файл:Treestep5_2.jpg|thumb|650px|итоговое дерево]]
Дерево строится рекурсивно, каждый раз длина строки уменьшается в два раза, а все фазы работают линейно.
Расход памяти на построение дерева также линеен(т.к на каждой фазе мы лишь строим и сливаем сжатые суффиксные деверья).
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
==См. также==
333
правки

Навигация