497
правок
Изменения
Нет описания правки
* Парам даются номера (условно, в массиве они и так есть): <tex>11-(0), 12-(1), 21-(2), 22-(3)</tex>
* Создаётся новая строка из номеров пар: <tex>1 0 1 2 3 2</tex>
* Из полученной строки создаётся [[Сжатое суффиксное дерево | суффикcное дерево]]:
[[Файл:tree101232.png|300px|thumb|right|суфдерево для сжатой строки]]
{|class="wikitable"
которого ограничены нечетными позициями <tex>1,3,5, \dots </tex> строки <tex>s\$</tex>.}}
Из чётного дерева, нужно получить нечётное дерево (дерево из суффиксов в нечётных позициях). Для этого можно взять [[Суффиксный массив | суффиксный массив ]] чётного дерева, отрезать первые символы, и выполнить стабильную сортировку по оставшимся первым символам:
[[Файл:odd.png|300px|thumb|right| нечетное дерево]]
|}
Для выяснения общего префикса строк, автор предлагает использовать находить общего предка вершин в [[Сжатое суффиксное дерево|суффиксном дереве. Считается ]] и считает, что такой предок можно найти за константное время. Для примера в этом дереве, общее начало строк '''5''' и '''9''' (11011111000 1111011111000) записано в пути от корня до общего предка этих вершин: (рис. 3-1)
[[Файл:treestep3_blue.jpg|400px|рис. 3-1]]
