В 2022 году Computer Science Center приостановил набор и обучение
Курсы
/
Алгоритмы и структуры данных, часть 2
/
весна 2015
/

Строки: суффиксное дерево, алгоритм Укконена

Понедельник, 30 марта 2015
Таймс, ауд. 404
Список тем / 2 записи
    1.
    Строки. Поиск подстрок
    2.
    Строки: суффиксное дерево, алгоритм Укконена

Описание

  • Суффиксное дерево. Основные свойства
  • Итеративный алгоритм построения за $O(N^2)$ дополнением символов в конец строки
  • Оптимизация размера дерева с помощью сжатия путей
  • Переход по суффиксной ссылке в сжатом дереве
  • Автоматическое продление листов
  • Итоговая линейная оценка