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

Question

Существует ли быстрая (O (1) временная сложность) способ генерации строки suffix tree строки S [2. .m] из дерева суффиксов строки S [1..m]?

Я знаком с Ukkonen, поэтому я знаю, как сделать дерево суффиксов строки S [1..m + 1] из дерева суффиксов строки S [1..m], но я не смог применить алгоритм обратной ситуации.

Answer 1

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

• Найти позиционно-0 лист L.
• Если L имеет более чем один родной брат, удалить указатель из L 'родителя s к L
• Если L имеет ровно один родственный, изменить указатель из L' s прародителей к L Родитель, а вместо этого указывает на L. Sibling.

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

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

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

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