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

слова...................................................................................165
71. Факторный оракул..............................................................................................167

Глава 5. Регулярные структуры в словах. ..............................................171
72. Три квадрата префиксов....................................................................................172
73. Точные границы количества вхождений степеней. ......................................174
74. Вычисление серий для алфавитов общего вида.............................................176
75. Проверка перекрытий в двоичном слове........................................................178
76. Игра, свободная от перекрытий........................................................................180
77. Заякоренные квадраты.......................................................................................182
78. Слова, почти свободные от квадратов.............................................................184
79. Двоичные слова с небольшим числом квадратов..........................................186
80. Построение длинных свободных от квадратов слов.....................................188
81. Проверка свободы морфизма от квадратов....................................................190
82. Число квадратных факторов в помеченных деревьях..................................192
83. Подсчет квадратов в гребнях за линейное время..........................................194
84. Кубические серии................................................................................................196
85. Короткий квадрат и локальный период..........................................................198
86. Число серий..........................................................................................................200
87. Вычислений серий над отсортированным алфавитом. ................................203
88. Периодичность и факторная сложность..........................................................207
89. Периодичность морфических слов..................................................................208
90. Простые антистепени.........................................................................................210
91. Палиндромическая конкатенация палиндромов..........................................211
92. Деревья палиндромов........................................................................................212
93. Неустранимые образцы. ....................................................................................214

Глава 6. Сжатие текста. ....................................................................................217
94. Преобразование Барроуза–Уилера слов Туэ–Морса. ....................................218
95. Преобразование Барроуза–Уилера сбалансированных слов. ......................219
96. Преобразование Барроуза–Уилера на месте. .................................................223
97. Факторизация Лемпеля–Зива. ..........................................................................225
98. Декодирование Лемпеля–Зива–Уэлча.............................................................227
99. Стоимость кода Хаффмана................................................................................229
100. Кодирование Хаффмана с ограничением на длину. ...................................232
101. Динамическое кодирование Хаффмана........................................................237
102. Кодирование длинами серий..........................................................................239
103. Компактный факторный автомат. .................................................................244
104. Сжатое сопоставление в слове Фибоначчи...................................................247
105. Предсказание по частичному совпадению...................................................249

8  Содержание
106. Сжатие суффиксных массивов........................................................................251
107. Коэффициент сжатия жадных суперстрок....................................................253

Глава 7. Разное.....................................................................................................257
108. Двоичные слова Паскаля. ................................................................................258
109. Самовоспроизводящиеся слова......................................................................260
110. Веса факторов....................................................................................................261
111. Разности вхождений букв................................................................................263
112. Факторизация с префиксами, свободными от границ................................265
113. Тест примитивности для унарных расширений. .........................................267
114. Частично коммутативные алфавиты.............................................................269
115. Наибольшее ожерелье фиксированной плотности......................................270
116. Двоичные слова, эквивалентные по периодам............................................272
117. Динамическое генерирование слов де Брёйна.............................................275
118. Рекурсивное генерирование слов де Брёйна................................................277
119. Уравнения в словах с заданными длинами переменных...........................279
120. Разнородные факторы над трехбуквенным алфавитом.............................281
121. Наибольшая возрастающая подпоследовательность..................................283
122. Неустранимые множества и слова Линдона.................................................285
123. Синхронизация слов.........................................................................................287
124. Сейфооткрывающие слова. .............................................................................289
125. Суперслова укороченных --">