Максим Крошемор , Тьерри Лекрок , Войцех Риттер - Алгоритмы обработки текста: 125 задач с решениями

125 Problems
in Text Algorithms
With Solutions

Maxime Crochemore, Thierry Lecroq, Wojciech Rytter

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

Максим Крошемор, Тьерри Лекрок, Войцех Риттер

Москва, 2021

УДК 004.912
ББК 81.112
К83

К83

Крошемор М., Лекрок Т., Риттер В.
Алгоритмы обработки текста: 125 задач с решениями / пер. с англ.
А. А. Слинкина. – М.: ДМК Пресс, 2021. – 312 с.: ил.
ISBN 978-5-97060-952-1
Сопоставление строк – одна из самых старых тем в теории алгоритмов, но
по-прежнему занимает важное место в информатике. За прошедшие 20 лет мы
видели технологические прорывы в таких разных приложениях, как информационный поиск и сжатие информации. Эта книга, представляющая собой богатое
собрание задач и упражнений по важнейшим вопросам алгоритмов обработки
текстов и комбинаторных свойств слов, предлагает студентам и исследователям
приятный и прямой путь к изучению и практическому освоению концепций повышенного уровня.
Задачи взяты из многочисленных научных публикаций – как уже ставших
классическими, так и сравнительно новых. Начав с основ, авторы рассматривают
все более сложные задачи по комбинаторным свойствам слов (включая слова Фибоначчи и Туэ–Морса), поиску строк в тексте (включая алгоритмы Кнута–Морриса–Пратта и Бойера–Мура), эффективным структурам данных для представления
текстов (включая суффиксные деревья и суффиксные массивы) и сжатия текста
(включая методы Хаффмана, Лемпеля–Зива и Барроуза–Уилера).
Издание будет полезно в качестве пособия для подготовки к олимпиадам по
информатике.

УДК 004.912
ББК 81.112

Copyright Original English language edition published by Cambridge University Press is part
of the University of Cambridge. Russian language edition copyright © 2021 by DMK Press. All
rights reserved.
Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения
владельцев авторских прав.

ISBN 978-1-108-83583-1 (англ.)
ISBN 978-5-97060-952-1 (рус.)

© Maxime Crochemore, Thierry Lecroq,
Wojciech Rytter, 2021
© Перевод, оформление, издание,
ДМК Пресс, 2021

Содержание
От издательства. .....................................................................................................9
Предисловие...........................................................................................................10
Глава 1. Первые понятия стрингологии....................................................12
Слова.............................................................................................................................13
Периодичность............................................................................................................14
Регулярные структуры. ..............................................................................................16
Упорядочение..............................................................................................................17
Примечательные слова..............................................................................................18
Автоматы. ....................................................................................................................20
Префиксные деревья..................................................................................................22
Суффиксные структуры. ............................................................................................22
Суффиксный массив...................................................................................................23
Сжатие..........................................................................................................................24
Соглашения о псевдокоде алгоритмов....................................................................25
Примечания.................................................................................................................26

Глава 2. Комбинаторные задачи. .................................................................27
1. Стрингологическое доказательство малой теоремы Ферма............................28
2. Простой случай проверки однозначности декодирования..............................29
3. Магические квадраты и слово Туэ–Морса..........................................................30
4. Последовательность Ольденбургера–Колакоски. ..............................................31
5. Бесквадратная игра. ...............................................................................................34
6. Слова Фибоначчи и фибоначчиева система счисления....................................36
7. Игра Витхоффа и слово Фибоначчи......................................................................38
8. Различные периодические слова. ........................................................................39
9. Вариации на тему слова Туэ–Морса. ...................................................................41
10. Слова Туэ–Морса и суммы степеней.................................................................42
11. Сопряженные слова и ротации слов. .................................................................43
12. Сопряженные палиндромы.................................................................................45
13. Много слов с большим числом палиндромов...................................................47
14. Короткое суперслово перестановок...................................................................48
15. Короткая суперпоследовательность перестановок. ........................................50
16. --">