Как эффективно извлечь исходную строку из дерева суффиксов?

Question

Если у нас есть дерево суффиксов строки, а также то, что дерево суффиксов не является деревом суффиксов ukkonen, т. Е. Нам дается нормальное дерево суффиксов, где метки ребер являются строками. Как эффективно вернуть исходную строку из этого дерева суффиксов?

Answer 1

Исходная строка имеет самый длинный суффикс, поэтому вы можете просто выполнить поиск в глубину, чтобы найти узел для самой длинной строки в дереве.