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

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