497
правок
Изменения
→Шаг 3: построение нечетного по четному
которого ограничены нечетными позициями <tex>1,3,5, \dots </tex> строки <tex>s\$</tex>.}}
Из чётного дерева нужно получить нечётное дерево (дерево из суффиксов в нечётных позициях). Для этого можно взять [[Суффиксный массив | суффиксный массив]] чётного дереваМы хотим получить лексикографически отсортированные нечетные суффиксы строки, отрезать первые символы и выполнить стабильную сортировку по оставшимся первым символам: которым воссановим нечетное дерево. Заметим, что все нечетные суффиксы представляют собой один символ, за которым дальше следует четный суффикс, которые у нас уже отсортированы. Тогда поразрядно отсортируем их за линейное время.
Для выяснения общего префикса строк автор предлагает находить общего предка вершин в [[Сжатое суффиксное дерево|суффиксном дереве]] и считает, что такой предок можно найти за константное время. Для примера в этом дереве, общее начало строк '''5''' и '''9''' (<tex>11011111000</tex> и <tex>1111011111000</tex>) записано в пути от корня до общего предка этих вершин: (рисунок 3-1)
