Алгоритмы обработки строк, Окулов С.М., 2020.
На материале задачи поиска подстроки в строке, решению которой посвящены работы многих профессионалов за последние 20-30 лет, показано, как построить занятия по информатике, чтобы побудить школьника к творчеству, развить у него вкус к решению исследовательских проблем.
Для школьников, преподавателей информатики, а также для студентов, выбравших информатику в качестве основной специальности. Книга может быть использована как в обычных школах при проведении факультативных занятий, так и в образовательных учреждениях с углубленным изучением информатики и математики.
Алгоритм Д. Кнута – Дж. Морриса – В. Пратта.
Это — один из самых известных алгоритмов решения задачи поиска образца Р в тексте Т, имеющий временную оценку О(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. Алгоритм Ю. Майерса.
Вместо заключения.
Приложения.
Купить .
Дата публикации:
Теги: учебник по программированию :: программирование :: Окулов :: алгоритм :: строки
Смотрите также учебники, книги и учебные материалы:
Следующие учебники и книги:
Предыдущие статьи:
