Алгоритмы обработки текста. 125 задач с решениями

Сопоставление строк - одна из самых старых тем в теории алгоритмов, но по-прежнему занимает важное место в информатике. За прошедшие 20 лет мы видели технологические прорывы в таких, например, приложениях, как информационный поиск и сжатие информации. Эта книга, представляющая собой богатое собрание задач и упражнений по важнейшим вопросам алгоритмов обработки текстов и комбинаторных свойств слов, предлагает приятный и прямой путь к их изучению и практическому освоению.

Задачи взяты из многочисленных публикаций - как уже ставших классическими, так и сравнительно новых. Начав с основ, авторы рассматривают все более сложные задачи по комбинаторным свойствам слов (включая слова Фибоначчи и Туэ-Морса), поиску строк в тексте (включая алгоритмы Кнута-Морриса-Пратта и Бойера-Мура), эффективным структурам данных для представления текстов (включая суффиксные деревья и суффиксные массивы) и сжатия текста (включая методы Хаффмана, Лемпеля-Зива и Барроуза-Уилера).
Издание будет полезно студентам, преподавателям, школьникам для подготовки к олимпиадам по информатике, а также широкому кругу разработчиков программного обеспечения.

Об авторах:
Максим Крошемор - заслуженный профессор университета Гюстава Эйфеля и Королевского колледжа Лондона. Является почетным доктором Хельсинкского университета. Автор более 200 статей по алгоритмам на строках и их приложениям, а также соавтор нескольких книг по этой теме.
Тьерри Лекрок - профессор факультета информатики в университете Руана-Нормандии, Франция. В настоящее время возглавляет исследовательскую группу по обработке информации в биологии и здравоохранении, созданную на базе лаборатории компьютерных наук, обработки информации и систем. Более десяти лет являлся одним из координаторов рабочей группы по стрингологии во Французском национальном центре научных исследований.
Войцех Риттер - профессор факультета математики, информатики и механики Варшавского университета. Автор многочисленных публикаций по автоматам, формальным языкам, параллельным алгоритмам и алгоритмам обработки текста. Соавтор нескольких книг на эти темы, в т. ч. «Efficient Parallel Algorithms», «Text Algorithms» и «Analysis of Algorithms and Data Structures». Член Европейской академии.