Строки: суффиксный массив

Понедельник, 16 марта 2015
Таймс, ауд. 404

Описание

  • Суффиксное дерево. Определение. Примеры использования.
  • Суффиксный массив. Построение с помощью сортировки.
  • Ускорение сортировки с помощью хешей.
  • Алгоритм построения за O(N log N)
  • Алгоритм Касаи
  • Примеры использования.
    • нахождение подстроки
    • нахождение наибольшего общего префикса
    • подсчет числа различных подстрок
    • нахождение наибольшей общей подстроки