Алгоритмы обработки строк, Окулов С.М., 2024.
На материале задачи поиска подстроки в строке, решению которой посвящены работы многих профессионалов за последние 20-30 лет, показано, как построить занятия по информатике, чтобы побудить школьника к творчеству, развить у него вкус к решению исследовательских проблем.
Для школьников, преподавателей информатики, а также для студентов, выбравших информатику в качестве основной специальности. Книга может быть использована как в обычных школах при проведении факультативных занятий, так и в образовательных учреждениях с углубленным изучением информатики и математики.
Алгоритм Р. Карпа - М. Рабина.
Алгоритм Р. Карпа - М. Рабина в «идейном» плане кардинально отличается от рассмотренных ранее методов, и его изучение — это необходимая составляющая образования специалиста по информатике, показывающая, как, казалось бы, «на ровном месте» можно находить новые результаты по преодолению ограниченности компьютера.
Ограничение на алфавит — А = {0, 1}. Это не столь принципиально, ибо, в конечном счете, строку вполне можно трактовать как двоичную последовательность. Пусть Р есть двоичная последовательность длины т, а Т — двоичная последовательность длины n. Как можно реализовать поиск вхождения Р в Т?
ОГЛАВЛЕНИЕ.
Предисловие.
Глава 1. Строки.
1.1. Основные понятия.
1.2. Методы предварительного анализа строк.
Глава 2. Классические алгоритмы решения задач обработки строк.
2.1. Алгоритм Д. Кнута - Дж. Морриса - В. Пратта.
2.2. Алгоритм Р. Бойера - Дж. Мура.
2.3. Алгоритм Р. Карпа - М. Рабина.
2.4. Алгоритм Shift-And.
2.5. Использование элементов теории автоматов в решении задач обработки строк.
2.6. Алгоритм М. Крочемора.
2.7. Алгоритм М. Мейна - Р. Лоренца.
Глава 3. Деревья суффиксов.
3.1. Основные понятия. Простые алгоритмы построения дерева суффиксов.
3.2. Алгоритм Э. Укконена.
3.3. Алгоритм Е. Мак-Крейга.
3.4. Суффиксные массивы.
3.5. Алгоритм А. Ахо - М. Корасик.
Глава 4. Вычисление расстояния между строками.
4.1. Основной алгоритм.
4.2. Алгоритм Э. Укконена - Ю. Майерса.
4.3. Задача о наибольшей общей подпоследовательности двух строк.
Глава 5. Алгоритмы приближенного поиска подстрок.
5.1. Простой алгоритм.
5.2. Алгоритм С. By - Ю. Менбера.
5.3. Задача о k-несовпадениях.
5.4. Алгоритм Ю. Майерса.
Вместо заключения.
Приложения.
Купить .
Дата публикации:
Теги: учебник по программированию :: программирование :: Окулов :: алгоритм :: строки
Смотрите также учебники, книги и учебные материалы:
Следующие учебники и книги:
Предыдущие статьи:
