Поиск в неявном суффиксном дереве, построенном по алгоритму Укконена

Question

Я столкнулся с проблемой, которая требует структуру данных, которая будет содержать строку S и позволит мне:

1. Проверьте, является ли слово W подсловом слова S за O(|W|)
2. Найти самый длинный суффикс S, который также является префиксом заданного слова U за O(|U|) время
3. Добавить строку K в конце S за O(|K|) время

Я понял, что деревья суффиксов, построенные по алгоритму Укконена, - это то, что я ищу. Алгоритм описывается как "Построение он-лайн суффиксных деревьев", и у меня есть проблема с "онлайновой" частью: после вставки каждого символа алгоритм строит неявное суффиксное дерево, которое может быть преобразовано в явное на последнем этапе. Но что, если я хочу использовать неявное дерево для поиска перед этим шагом? "онлайн" предполагает, что это возможно после вставки любого префикса анализируемой строки, но я не могу найти ни одного примера даже самого простого алгоритма, который работает с неявным деревом.

Мой вопрос: как мне найти строку в неявном дереве суффиксов?

РЕДАКТИРОВАТЬ: я принял очень хороший ответ, который решает мою проблему, но в то же время мне удалось найти более простое решение для 2: достаточно найти U с суффиксом S длины | U | с использованием алгоритма KMP, и последним количеством совпавших символов будет совпадение строк.

Answer 1

Существует только одно различие между неявным суффиксным деревом и явным суффиксным деревом: оно не содержит маркеров конца строки (и не содержит ветвей, соответствующих этим маркерам конца строки).

Это означает, что нет разницы, где искать подстроку - в неявном дереве суффиксов или в явном дереве суффиксов. Поскольку неявное суффиксное дерево содержит меньше ненужных ветвей, это гарантирует еще более эффективный (но все еще линейный) алгоритм поиска подстроки.

Таким образом, требование № 1 выполняется автоматически: просто найдите дерево суффиксов в корне и выберите ветви, соответствующие данному слову.

Что касается требования № 2, я думаю, вы не можете удовлетворить его тем же неявным деревом суффиксов. Потому что вам нужны маркеры конца строки для работы с суффиксами.

Но вы могли бы сделать это в O(|U|) время с отдельным (явным) деревом суффиксов для данного слова U, Хитрость заключается в том, чтобы перевернуть это слово перед созданием дерева суффиксов. Чтобы найти самый длинный суффикс S это также префикс U, используйте это отдельное дерево суффиксов, чтобы найти самый длинный префикс обратной строки S это также суффикс обратной строки U, Просто найдите это дерево суффиксов в корне, выберите ветви, соответствующие обратной строке Sи запомните последний узел с маркером конца строки. Затем переверните строку на пути от корня к этому узлу (или определите длину этого пути и скопируйте подстроку той же длины из хвоста S).