Строки: суффиксное дерево, алгоритм Укконена

Понедельник, 30 марта 2015

Таймс, ауд. 404

Список тем / 2 записи

Строки. Поиск подстрок

2.

Строки: суффиксное дерево, алгоритм Укконена

Описание

Суффиксное дерево. Основные свойства
Итеративный алгоритм построения за $O(N^2)$ дополнением символов в конец строки
Оптимизация размера дерева с помощью сжатия путей
Переход по суффиксной ссылке в сжатом дереве
Автоматическое продление листов
Итоговая линейная оценка