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