Палиндромное дерево

Палиндромное дерево
Тип	Дерево
Изобретенный	2015
Изобретён	Михаил Рубинчик, Арсений Михайлович Шур
Временная сложность в обозначении большого О Операция Средний Худший случай Поиск О ( п * журнал σ ) О ( п * журнал σ ) Вставлять О( журнал σ ) На ​ ) Пространственная сложность Космос На ​ ) На ​ )

В информатике дерево -палиндром , также называемое EerTree, это тип дерева поиска , который обеспечивает быстрый доступ ко всем палиндромам, содержащимся в строке . Их можно использовать для решения самой длинной палиндромной подстроки , задачи k -факторизации. (можно ли данную строку разделить ровно на k палиндромов), палиндромная длина строки (какое минимальное количество палиндромов необходимо для построения строки), а также поиск и подсчет всех различных субпалиндромов. Деревья-палиндромы делают это онлайн , то есть не требуется вся строка в начале и ее можно добавлять посимвольно .

Описание

Пример дерева-палиндрома для TACOCAT, где сплошные линии — это края символов, а пунктирные линии — это края суффикса.

Как и большинство деревьев, дерево-палиндром состоит из вершин и направленных ребер. Каждая вершина в дереве представляет собой палиндром (например, «такокат»), но хранит только длину палиндрома, а каждое ребро представляет собой либо символ, либо суффикс . Ребра символа означают, что когда символ добавляется к обоим концам палиндрома, представленного исходной вершиной, создается палиндром в целевой вершине (например, ребро с меткой «t» будет соединять исходную вершину «acoca» с целевой вершиной). «такокат»). Ребро суффикса соединяет каждый палиндром с самым большим суффиксом палиндрома, которым он обладает (в предыдущем примере «tacocat» будет иметь суффиксное ребро с «t», а «atacocata» будет иметь суффиксную ссылку с «ata»). Палиндромные деревья отличаются от обычных деревьев тем, что у них два корня (поскольку на самом деле это два отдельных дерева). Два корня представляют собой палиндромы длины -1 и 0. То есть, если к обоим корням добавить символ «а», дерево создаст «а» и «аа» соответственно. Поскольку каждое ребро добавляет (или удаляет) четное количество символов, два дерева всегда соединяются только суффиксными ребрами.

Операции

Добавлять

Поскольку дерево палиндромов следует онлайн-конструкции, оно сохраняет указатель на последний палиндром, добавленный в дерево. Чтобы добавить следующий символ в дерево палиндромов, add(x) сначала проверяет, соответствует ли первый символ перед палиндромом добавляемому символу; если нет, то по суффиксным ссылкам следуют до тех пор, пока палиндром не будет добавлен в дерево. Если палиндром найден, если он уже существовал в дереве, ничего делать не нужно. В противном случае добавляется новая вершина со ссылкой из суффикса на новую вершину и добавляется суффиксная ссылка для новой вершины. Если длина нового палиндрома равна 1, суффиксная ссылка указывает на корень дерева палиндромов, который представляет длину -1.

# S -> Input String
# x -> position in the string of the character being added
def add(x: int) -> bool:
    """Add character to the palindrome tree."""
    while True:
        if x - 1 - current.length >= 0 and S[x - 1 - current.length] == S[x]:
            break
        current = current.suffix

    if current.add[S[x]] is not None:
        return False

    suffix = current
    current = Palindrome_Vertex()
    current.length = suffix.length + 2
    suffix.add[S[x]] = current

    if current.length == 1:
        current.suffix = root
        return True

    while True:
        suffix = suffix.suffix
        if x - 1 - suffix.length >= 0 and S[x - 1 - suffix.length] == S[x]:
            current.suffix = suffix.add[S[x]]
            return True

Совместные деревья

Найти палиндромы, общие для нескольких строк или уникальные для одной строки, можно с помощью $O(n*i)$ дополнительное пространство, где $i$ — количество сравниваемых строк. Это достигается добавлением массива длиной $i$ к каждой вершине и установив флаг в 1 по индексу $i$ если эта вершина была достигнута при добавлении строки $i$. Единственное необходимое изменение — это сбросить текущий указатель на корень в конце каждой строки. Соединяя деревья таким образом, можно решить следующие проблемы:

• Количество палиндромов, общих для всех строк
• Количество уникальных палиндромов в строке
• Самый длинный палиндром, общий для всех строк
• Количество палиндромов, которые встречаются в одной строке чаще, чем в других.

Сложность

Время

Построение дерева-палиндрома занимает $O(n\log {\sigma })$ время, где $n$ длина строки и $\sigma$ размер алфавита. С $n$ звонки в add(x), каждый звонок занимает $O(\log {\sigma })$ амортизированное время. Это результат каждого вызова add(x) увеличивает глубину текущей вершины (последнего палиндрома в дереве) не более чем на единицу, а поиск всех возможных ребер символов вершины занимает $O(\log {\sigma })$ время. Назначая стоимость перемещения вверх и вниз по дереву каждому вызову add(x), стоимость перемещения вверх по дереву более одного раза «оплачивается» равным количеством вызовов add(x) при движении вверх по дереву не происходило.

Космос

Дерево-палиндром занимает $O(n)$ пространство: Максимум $n+2$ вершины для хранения подпалиндромов и двух корней, $n$ ребра, соединяющие вершины и $n+2$ суффиксные края.

Компромисс между пространством и временем

Если вместо хранения только добавленных ребер, существующих для каждого палиндрома, массив длины $\sigma$ сохраняется, поиск правильного края может быть выполнен за постоянное время, что сокращает время строительства до $O(n+p*\sigma )$ одновременно увеличивая пространство до $O(p*\sigma )$, где $p$ это количество палиндромов.