Изменения

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

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

54 байта добавлено, 14:52, 8 июня 2014
Шаг 3: построение нечетного по четному
Для выяснения Выяснение общего префикса строк автор предлагает можно находить общего предка вершин в [[Сжатое суффиксное дерево|суффиксном дереве]] и считает, что такой предок . Такого предка можно найти за [[константное время, потратив <tex>O(n)</tex> на препроцессинг| http://e-maxx.ru/algo/lca_linear ]]. Для примера в этом дереве, общее начало строк '''5''' и '''9''' (<tex>11011111000</tex> и <tex>1111011111000</tex>) записано в пути от корня до общего предка этих вершин: (рисунок 3-1)
[[Файл:treestep3_blue.jpg|400px|рисунок 3-1]]
497
правок

Навигация