Алгоритмы обработки строк
Книга посвящена задаче поиска подстроки в строке — одной из классических проблем информатики, исследованием которой занимались ведущие специалисты последних десятилетий. На примере этой задачи показано, как построить занятия по информатике, чтобы развить у школьников творческое мышление и исследовательские навыки.
В книге подробно рассматриваются классические алгоритмы обработки строк: Кнута-Морриса-Пратта, Бойера-Мура, Карпа-Рабина, Shift-And, а также более сложные структуры данных, такие как деревья суффиксов и суффиксные массивы. Отдельные главы посвящены вычислению расстояния между строками и алгоритмам приближенного поиска подстрок.
Материал изложен доступно для школьников, но при этом сохраняет научную глубину. Книга может использоваться как для факультативных занятий в обычных школах, так и в образовательных учреждениях с углубленным изучением информатики и математики.
