Теория
- Ссылки
- (link) [страничка ИТМО]
- (link) [работа Димы Паращенко]
- Старое
- Опредление суфф. автомата. Получение автомата из суфф. дерева (в теории, без алгоритма).
- Правые контексты. Rw(s), равенство правых контекстов.
- Состояние = множество строк с одинаковым правым контекстом
- Состояние = самая длинная стока длины len[v] + несколько ее суффиксов.
- Суфф. ссылка = максимальный по длине суффикс, не вошедший в состояние
- Конечные состояния автомата (те состояния, где заканчиваются суффиксы строки) = путь по суфф. ссылкам от конца до корня
- Добавление к строке нового символа. Откат по суфф. ссылкам и добавление ребер. Недетерменированный автомат.
- Делаем автомат детерменированным. Когда нужно раздваивать вершину?
- Новое
- Док-во времени работы автомата O(N)
- суфф. дерево <-> суфф. массив
- суфф. дерево <-> суфф. автомат
Практика
- 110304a1 : 5G (число подстрок)
- 110304a1 : 5D (бывший Укконен)
- 110304a1 : 5E (динамика по автомату)
- Задачи A, B, C, F