Теория

  1. Ссылки
    1. (link) [страничка ИТМО]
    2. (link) [работа Димы Паращенко]
  2. Старое
    1. Опредление суфф. автомата. Получение автомата из суфф. дерева (в теории, без алгоритма).
    2. Правые контексты. Rw(s), равенство правых контекстов.
    3. Состояние = множество строк с одинаковым правым контекстом
    4. Состояние = самая длинная стока длины len[v] + несколько ее суффиксов.
    5. Суфф. ссылка = максимальный по длине суффикс, не вошедший в состояние
    6. Конечные состояния автомата (те состояния, где заканчиваются суффиксы строки) = путь по суфф. ссылкам от конца до корня
    7. Добавление к строке нового символа. Откат по суфф. ссылкам и добавление ребер. Недетерменированный автомат.
    8. Делаем автомат детерменированным. Когда нужно раздваивать вершину?
  3. Новое
    1. Док-во времени работы автомата O(N)
    2. суфф. дерево <-> суфф. массив
    3. суфф. дерево <-> суфф. автомат

Практика

  1. 110304a1 : 5G (число подстрок)
  2. 110304a1 : 5D (бывший Укконен)
  3. 110304a1 : 5E (динамика по автомату)
  4. Задачи A, B, C, F