Генерирование дерева суффиксов строки S [2..m] из дерева суффиксов строки S [1..m]

Ответ 1

Хорошо, как говорит @jogojapan, чтобы получить дерево S [2..m] из дерева S [1..m], нам нужно:

• Найдите позицию-лист L.
• Если L имеет более одного брата, удалите указатель из L parent в L
• Если L имеет ровно один родственный брат, измените указатель от L grandparent на родительский L, чтобы он вместо этого указывал на L sibling.

@jogojapan далее предполагает, что вы держите указатель на самый глубокий лист в дереве. Есть две проблемы с этим: L не обязательно самый глубокий лист в дереве, так как Пример Википедии показывает, а второй, если вы хотите быть способный выводить структуру данных того же типа, что и вы получили, после удаления L вам нужно найти новый лист position-0, который в любом случае займет время O (m).

(Что вы можете сделать, так это построить массив указателей на каждый лист в O (m) time и count - отсортировать их по положению в другое время O (m). Тогда вы сможете построить все деревья { S [t..n]: 1 <= t <= m} в течение постоянного времени амортизации)

Предполагая, что вы не заинтересованы в амортизированном времени, пусть докажет, что вы просите, невозможно.

• Мы знаем, что любой алгоритм для изменения дерева суффиксов S [1..m] должен начинаться с корня: он не может начинаться нигде, потому что мы ничего не знаем о базовой структуре конкретных данных, и мы не знаем что узлы дерева имеют родительские указатели, поэтому единственной позицией, доступной для всего дерева, является корень.
• Мы также знаем, что он должен найти лист позиции-0, прежде чем он сможет надеяться изменить структуру данных в дереве суффиксов для S [2..m]. Для этого он должен, очевидно, пересечь каждый node между корнем и листом position-0.
• Вещь, рассмотрим дерево суффикса a ^ m (символ повторяется m раз): длина пути m-1. Таким образом, любой алгоритм должен посещать как минимум m-1 узлы и, следовательно, принимать O (m) время в худшем случае.