Введение
1 Введение 5
1.1 Структура диссертации и организация текста 6
1.2 Предварительные сведения
1.2.1 Понятия из стрингологии 9
1.2.2 Модель вычисления Word-RAM 10
1.2.3 Типы алгоритмических задач 11
1.2.4 Структуры данных 12
1.2.5 Исходные коды программ 13
1.2.6 Используемые структуры данных 13
1.3 Обзор результатов диссертации 15
1.3.1 Цели, задачи и основные результаты 16
1.3.2 Научная новизна, значимость и корректность результатов 17
1.3.3 Основные методы исследования 17
1.3.4 Апробация и публикации 17
1.4 Благодарности 19
2 Палиндромы 20
2.1 Введение 20
2.1.1 Определения и обозначения 21
2.2 Овердрево 21
2.2.1 Побуждающая задача: поиск подпалиндромов онлайн 21
2.2.2 Интерфейс структуры данных 26
2.2.3 Внутреннее устройство структуры данных 26
2.2.4 Простой онлайн-алгоритм 27
2.2.5 Некоторые свойства овердрева 29
2.2.6 Задачи, иллюстрирующие возможности овердрева 31
2.3 Вариации овердрева и некоторые их приложения 36
2.3.1 Совместное овердрево для нескольких строк 36
2.3.2 Поиск с откатами 38
2.3.3 Подсчёт палиндромно-насыщенных строк 42
2.3.4 Поиск подпалиндромов на дереве 45
2.4 Задачи о разбиении на подпалиндромы 47
2.4.1 Простое решение за O(kn + n log n) 48
2.4.2 Разбиение на k палиндромов и поиск палиндромной длины 49
2.4.3 Решение задачи о палиндромной длине 50
2.4.4 Гипотеза о линейном решении 55
3 Повреждённые строки 60
3.1 Введение 60
3.2 Предварительные сведения
3.2.1 Основные определения 61
3.2.2 Исторический обзор 61
3.3 Задача максимизации числа вхождений 63
3.3.1 Решение для неповреждённого текста 63
3.3.2 Решение для неповреждённого шаблона 64
3.3.3 Доказательство NP-трудности в общем случае 65
3.4 Задача минимизации расстояния Хэмминга 68
3.4.1 Случай неповреждённого текста 68
3.4.2 Случай неповреждённого шаблона 69
3.4.3 Случай частичных строк с циклическим текстом 69
3.4.4 Случай бинарного алфавита 70
3.4.5 Случай частичных строк и задача о мультиразрезе 71
3.4.6 Доказательство NP-трудности в общем случае 72
Заключение 75
Список литературы
