Теория

1. Ссылки
1. (link) [страничка ИТМО]
2. (link) [работа Димы Паращенко]
2. Старое
1. Опредление суфф. автомата. Получение автомата из суфф. дерева (в теории, без алгоритма).
2. Правые контексты. R_w(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