Поиск образца: один текст и много образцов (online). Суффиксный бор. Поиск вхождений образца на суфф. боре. Размер бора O(T^2). Алгоритм Укконена. Положения в дереве: явные и неявные. Строим дерево, добавляя по одному символу (итерации) слева направо. Удлиняем суффиксы в дереве (шаги) в пор-ке уменьшения длины. Три типа шагов. O(T) шагов второго типа (ветвлений). Шаги третьего типа (проходы) делать не нужно. Бесплатное выполнение шагов первого типа (листьев). Все продолжения вершины AB являются продолжениями вершины B. Упорядоченность типов шагов на итерации. Старт итерации: в том месте, где на пред. итерации был первый шаг третьего типа. Суффиксная ссылка. Точка ветвления переходит (по суфф. ссылке) в т.ветв. Храним значения суфф. ссылок в т.ветв. Вычисление суфф. ссылки от неявного положения, случай с корнем. Анализ времени работы. Путь алгоритма, его длина O(T). Вершинная глубина. Связь изменения вершинной глубины и времени вычисления суффиксной ссылки. Суммарное время вычисления суффиксных ссылок O(T).
Лекция №3 в курсе "Алгоритмы и структуры данных, часть 2", весна 2018 (Новосибирск)
Преподаватели курса: Александр Александрович Стененко, Степан Юрьевич Гатилов
Страница лекции на сайте CS центра: goo.gl/U7LJTv
Все видео курса по порядку: goo.gl/b8KQcs