Я просто изучаю суффиксные деревья / попытки и пытаюсь сначала реализовать его с помощью некоторого тривиального алгоритма (нелинейного). Тривиальный алгоритм требует последовательного добавления суффиксов строки, и на некотором этапе у нас может быть некоторый суффикс, который будет префиксом другого суффикса, который требует пересечь этот уже существующий префикс.
Например, есть строка «банан». Здесь у нас есть следующие суффиксы:
banana$
anana$
nana$
ana$
na$
a$
Теперь давайте предположим, что мы добавили первые 3 суффикса в дерево, и в настоящее время нам нужно добавить ana . Это означает, что нам нужно сначала пройти anana и найти самый длинный префикс, например ana , а затем добавить его. Так требует ли это go построения tr ie перед построением дерева?