Актуальность темы исследования. Строка (последовательность
символов) — один из центральных объектов компьютерных наук. Любые
данные, имеющие линейную структуру (например, текст на естественном или искусственном языке, лог сервера или колебания курса валюты) можно представить в виде строки и изучать особенности в этой
строке. Начало активного изучения алгоритмов, связанных со строками, приходится на 1970е годы. Раздел компьютерных наук, посвящённый изучению алгоритмов обработки строк, называется стрингологией (stringology). Впервые это название было предложено в 1985 в работе [11], когда область уже имела какой-то набор результатов, но сложно
было назвать её отдельной наукой. Однако уже в 90х годах наблюдается
стремительный рост числа публикаций по данной тематике. Одной из
самых сильных предпосылок развития является появление биоинформатики, науки, изучающей «биологические строки» (ДНК, РНК, белки
и др.). Именно биоинформатика породила множество задач, изучаемых
стрингологами. Не менее важным источником задач являются современные информационные технологии, требующие эффективных алгоритмов анализа и обработки данных. Среди задач этой группы выделяются
задача поиска в массиве данных и задача сжатия данных. Кроме того, стрингология, относимая к фундаментальной информатике, решает
большое число чисто математических задач, не нашедших еще практического применения. Сюда относится, в частности, классификация задач о строках по их вычислительной сложности. Многие теоретические
задачи приходят в стрингологию из комбинаторики слов.
