Алгоритмы обработки строк, Окулов С.М., 2015

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




Алгоритм Г. Ландау - Ю. Вишкина.
В алгоритме Г. Ландау - Ю. Вишкина задача о k-несовпадениях решается с несколько других позиций. Используется метод предварительного анализа образца, но он отличается от ранее рассмотренных (от выделения граней префиксов или блоков строки).

Обратимся для «вычленения» ключевой идеи алгоритма к примеру. Пусть Т, Р и k те же, что и в ранее рассмотренной модификации алгоритма Shift-And. В табл. 5.7 представлена обычная логика поиска образца в тексте. Единственное отличие — при каждом прикладывании образца к тексту в соответствующей строке матрицы несовпадений (рс) фиксируются номера позиций несовпавших символов Р. Первоначально рс заполняется значением m + 1.

ОГЛАВЛЕНИЕ.
Предисловие.
Глава 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. Алгоритм Ю. Майерса.
Вместо заключения.
Приложения.

Купить .








Теги: учебник по программированию :: программирование :: Окулов :: алгоритм :: строки