Введение
1 Введение 4
1.1 Структура диссертации и организация текста 4
1.2 Основные методы исследования 6
1.3 Базовые определения
1.3.1 Основные понятия 7
1.3.2 Закономерности в строках 8
1.4 Модель RAM 10
1.4.1 Доступные инструкции и память 10
1.4.2 Входные данные 11
1.4.3 Время выполнения
1.5 Модель решающего дерева 14
1.6 Обзор результатов
1.6.1 Апробация и публикации 15
1.6.2 Разложение Лемпеля–Зива 15
1.6.3 Повторы в строках 16
1.6.4 Палиндромы 18
2 Разложение Лемпеля–Зива 19
2.1 Введение 19
2.2 Нижняя граница 19
2.3 Сжатый алгоритм поиска разложения Лемпеля–Зива
2.3.1 Короткие факторы 22
2.3.2 Средние факторы 22
2.3.3 Длинные факторы 39
3 Повторывстроках 46
3.1 Введение 46
3.2 Поиск максимальных повторов на решающем дереве
3.2.1 Максимальные повторы 48
3.2.2 Алгоритмы на решающих деревьях 50
3.2.3 Линейное решающее дерево 52
3.3 Поиск максимальных повторов за o(n log n) 57
3.3.1 Сведение к разреженному суффиксному дереву 57
3.3.2 Построение разреженного суффиксного дерева 58
3.4 Онлайновый поиск повторов с откатами 61
3.4.1 Ловец 62
3.4.2 Алгоритм на неупорядоченном алфавите 65
3.4.3 Алгоритм на упорядоченном алфавите 67
Палиндромы 71
4.1 Введение 71
4.2 Нижняя граница на поиск различных подпалиндромов 72
4.3 Распознаватель Palk и других палиндромных языков
4.3.1 Свойства палиндромов 74
4.3.2 Палиндромный итератор 76
4.3.3 Палиндромный мотор 78
4.3.4 Линейный алгоритм 81
Заключение 90
Список литературы
