Книга: Окулов С. М. «Алгоритмы обработки строк»

Серия: "Развитие интеллекта школьников"

На материале задачи поиска подстроки в строке, решению которой посвящены работы многих профессионалов за последние 20–30 лет, показано, как построить занятия по информатике, чтобы побудить школьника к творчеству, развить у него вкус к решению исследовательских проблем.
Для школьников, преподавателей информатики, а также для студентов, выбравших информатику в качестве основной специальности. Книга может быть использована как в обычных школах при проведении факультативных занятий, так и в образовательных учреждениях с углубленным изучением информатики и математики.

Содержание:

Предисловие...... 5 Глава 1. Строки...... 9 1. 1. Основные понятия...... 9 1. 2. Методы предварительного анализа строк...... 13 Глава 2. Классические алгоритмы решения задач обработки строк...... 28 2. 1. Алгоритм Д. Кнута – Дж. Морриса – В. Пратта...... 28 2. 2. Алгоритм Р. Бойера – Дж. Мура...... 36 2. 3. Алгоритм Р. Карпа – М. Рабина...... 52 2. 4. Алгоритм Shift-And...... 57 2. 5. Использование элементов теории автоматов в решении задач обработки строк...... 73 2. 6. Алгоритм М. Крочемора...... 81 2. 7. Алгоритм М. Мейна – Р. Лоренца...... 88 Глава 3. Деревья суффиксов...... 103 3. 1. Основные понятия. Простые алгоритмы построения дерева суффиксов...... 103 3. 2. Алгоритм Э. Укконена...... 118 3. 3. Алгоритм Е. Мак-Крейга...... 127 3. 4. Суффиксные массивы...... 136 3. 5. Алгоритм А. Ахо – М. Корасик...... 147 Глава 4. Вычисление расстояния между строками...... 155 4. 1. Основной алгоритм...... 155 4. 2. Алгоритм Э. Укконена – Ю. Майерса...... 165 4. 3. Задача о наибольшей общей подпоследовательности двух строк...... 174 Глава 5. Алгоритмы приближенного поиска подстрок...... 198 5. 1. Простой алгоритм...... 198 5. 2. Алгоритм С. Ву – Ю. Менбера...... 201 5. 3. Задача о k-несовпадениях...... 205 5. 4. Алгоритм Ю. Майерса...... 215 Вместо заключения...... 225 Приложения...... 234

Издательство: "БИНОМ. Лаборатория знаний" (2015)

ISBN: 9785996326228