Дерево палиндромов
структура данных, предназначенная для хранения и обработки палиндромных подстрок некоторой строки / Материал из Википедии — свободной encyclopedia
Уважаемый Wikiwand AI, давайте упростим задачу, просто ответив на эти ключевые вопросы:
Перечислите основные факты и статистические данные о Дерево палиндромов?
Кратко изложите эту статью для 10-летнего ребёнка
Дерево палиндромов (англ. palindromic tree, также овердрево[1], англ. eertree) — структура данных, предназначенная для хранения и обработки палиндромных подстрок некоторой строки. Была предложена учёными из Уральского федерального университета Михаилом Рубинчиком и Арсением Шуром в 2015 году. Представляет собой два префиксных дерева, собранных из правых «половинок» палиндромных подстрок чётной и нечётной длины соответственно. Структура занимает памяти и может быть построена за время , где — длина строки, а — количество различных символов в ней. С помощью дерева палиндромов можно эффективно решать такие задачи, как подсчёт числа различных палиндромных подстрок, поиск разбиения строки на наименьшее число палиндромов, проверка подстроки на то, является ли она палиндромом, и другие.
Дерево палиндромов | |||||||
---|---|---|---|---|---|---|---|
англ. eertree | |||||||
| |||||||
Тип | структура данных | ||||||
Год изобретения | 2015 | ||||||
Автор | Михаил Рубинчик[вд] | ||||||
Сложность в О-символике | |||||||
|
|||||||
Медиафайлы на Викискладе |