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