Суффиксное дерево

  1. [Сережа.K] Суффиксное дерево
    1. Сжатое суф.дерево. Хранение.
    2. Построение за O(n) из суф.массива + LCP
    3. Алгоритм Укконена за O(n2) без суффиксных ссылок
      1. Листья растут сами
      2. Разветвляется самый длинный неразветвленный суффикс
      3. Позицию следующего суффикса ищем за линию
    4. Алгоритм Укконена за O(n)
      1. Суф.ссылка. Подсчет суф.ссылок.
      2. Инвариант: количество вершин на пути до корня, суммарное время работы = O(n)
  2. [Сережа.K] Skew Heap
    1. Сливаемые кучи: все операции выражаются через Merge
    2. Merge в Skew Heap: короткий волшебный код. И непонятно, почему быстро работающий.