Суф. дерево

  1. Опередление.
  2. Сжатое суф. дерево.
  3. Алгоритм построения за O(N2).

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

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

Суф. массив

  1. Сортировка подсчетом
  2. Цифоравая сортировка
  3. Сортировка строк за O(N2), построение суф. массива за O(N2).

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

  1. Суф. массив в суф. дерево
  2. Суф. дерево в суф. массив