Лекция 3. Суффиксное дерево

Поиск образца: один текст и много образцов (online). Суффиксный бор. Поиск вхождений образца на суффиксном боре. Размер бора O(T^2). Сжатие цепочек в боре → суффиксное дерево размера O (T). Алгоритм Укконена. Положения в дереве: явные и неявные. Строим дерево, добавляя по одному символу или итерации слева направо.

Удлиняем суффиксы в дереве (шаги) в пор-ке уменьшения длины. Три типа шагов. O (T) шагов второго типа — ветвлений. Шаги третьего типа или проходы делать не нужно. Бесплатное выполнение шагов первого типа — листьев. Все продолжения вершины AB являются продолжениями вершины B. Упорядоченность типов шагов на итерации. Старт итерации: в том месте, где на пред. итерации был первый шаг третьего типа. Суффиксная ссылка.

Вычисление суффиксной ссылки от неявного положения, случай с корнем. Анализ времени работы. Путь алгоритма, его длина O (T). Вершинная глубина. Связь изменения вершинной глубины и времени вычисления суффиксной ссылки. Суммарное время вычисления суффиксных ссылок O (T).