Применение равномерно разреженных суффиксных деревьев для задач обработки строк

С. Ф. Свиньин^a, И. А. Андрианов<sup>b

a</sup> Федеральное государственное бюджетное учреждение науки Санкт-Петербургский институт информатики и автоматизации РАН
^b Вологодский государственный университет

Аннотация: Потребность в эффективных алгоритмах обработки строк возникает во многих практических задачах. Одним из наиболее универсальных подходов является применение суффиксных деревьев. Однако, данная структура имеет высокие требования к памяти, что ограничивает область её применения. В данной статье на примере задачи о максимальной симметричной подстроке рассматривается способ, позволяющий частично устранить данный недостаток. Описанный способ может быть использован и для других задач.

Ключевые слова: информационный поиск, разреженные суффиксные деревья, ближайший общий предок, максимальный палиндром, алгоритм Укконена.

УДК: 681.3.07