Изменения

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

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

77 байт добавлено, 12:11, 14 июня 2014
Шаг 3: построение нечетного по четному
* Заметим, что все нечетные суффиксы представляют собой один символ, за которым дальше следует четный суффикс, которые у нас уже были отсортированы в суффиксном массиве. Тогда отсортируем их по первому символу за линейное время.
* [[Сжатое_суффиксное_дерево#.D0.9F.D0.BE.D1.81.D1.82.D1.80.D0.BE.D0.B5.D0.BD.D0.B8.D0.B5_.D0.B8.D0.B7_.D1.81.D1.83.D1.84.D1.84.D0.B8.D0.BA.D1.81.D0.BD.D0.BE.D0.B3.D0.BE_.D0.BC.D0.B0.D1.81.D1.81.D0.B8.D0.B2.D0.B0 | Построить из нового суффиксного массива дерево]], которое будет уже нечётным, что тоже делается за линейное время.
 
[[Файл: Odd.jpg|thmb|450px|Слитое дерево (условно)]]
Таким образом <tex>T_{odd}</tex> может быть построено за линейное время по <tex>T_{even}</tex>.
497
правок

Навигация