Бор, сжатый бор, алгоритм Укконена (17 апреля 2014)

1. Реализации
1. Бор. Несжатый. На массивах. [code]
2. Бор. Сжатый. Построение суфф.дерева за O(n²) и O(n) памяти [code]
2. Алгоритм Укконена построения суфф.дерева за O(n)
1. Онлайн алгоритм: нужно все суффиксы удлинить на 1
2. Жизненный цикл суффикса: движется по дереву, порождает новое разветвление и лист, удлиняет лист
3. Разветвляется в первую очередь самый длинный не разветвившийся суффикс (Lm: если i не разветвился, то ∀j > i: j тоже не разветвился
4. Осталось быстро переходить к следующему суффиксу (отрезать один символ). Для этого будем поддерживать от всех вершин суфф.ссылку. Суфф.ссылка от вершины − обязательно вершина.
5. suf[v] = Down(suf[parent[v]]). Линейнойсть времени работы: смотрим на величину "количество вершин на пути до корня". suf[] и parent[] уменьшают на 1, Down на каждом шагу увеличивает
3. Реализация Укконена
1. Текущая позиция: (v,char,position). Можно пытаться вместо (v,char) хранить edge, но тогда неудобно задавать корень.
2. Суфф.ссылки будем считать лениво. Причем запоминать суфф.ссылку будем только если она ведет в вершину.
3. Когда строим суфф.дерево для фиксированной строки (нам не нужна online-овость), можно создавать лист, как ребро edge(s_i, i, n-i), где n − длина строки
4. Реализация за O(n²): [code]
5. Реализация за O(n): [code]
4. Преобразование структур
1. Массив → Дерево. O(n).
2. Дерево → Массив. O(n).
3. Автомат → Дерево. O(n).
4. Автомат обратной строки → Дерево. O(n).