Алгоритм Укконена построения суф. дерева за O(N).

  1. Online-овость (этот алгоритм лучше уже тем, что можно Online наращивать строку)
  2. Добавление одного символа. Листья растут сами, без нашей помощи.
  3. Доказательство того, что более короткий суффикс станет листом не ранее более длинного.
  4. Суф. ссылки. Подсчет суфф. ссылок.
  5. Собственно алгоритм.
  6. Доказательство времени работы O(n).

Суф. массив. Часть 2

  1. Сортировка суффиксов и сортировка циклических сдвигов (как они друг к другу сводятся)
  2. Сортировка подсчетом
  3. Цифровая сортировка
  4. Сортировка строк за O(N2), построение суф. массива за O(N2).
  5. Построение LCP за O(NlogN) (хэши с бинпоиском)
  6. LCP[i,i+1] за O(N) (алгоритм Касаи)

Преобразования суф. структур

  1. Суф. массив + LCP → суф. дерево за O(n)
  2. Суф. дерево → суф. массив + LCP за O(n)

Решение задач суф. массивом и суф. деревом

  1. refrain (максимизировать величину "длина * число вхождений")
  2. Найти количество подстрок
  3. Найти подстроку макс длины, встречающуюся дважды, вхождения могут перекрываться
  4. Найти подстроку макс длины, встречающуюся дважды, вхождения не могут перекрываться