очень трудно понять суффиксное дерево

Я довольно долго искал туториалы по суффиксному дереву. В SO я нашел 2 сообщения о понимании дерева суффиксов: 1, 2.

Но я не могу сказать, что понимаю, как его построить, упс. В книге Скиены «Руководство по проектированию алгоритмов» он говорит:

Поскольку алгоритмы построения дерева суффиксов линейного времени нетривиальны, Я рекомендую использовать существующую реализацию.

Ну что, алгоритм построения суффиксного дерева он-лайн так сложен? Кто-нибудь может поставить меня в правильном направлении, чтобы понять это?

В любом случае, переходим к делу, кроме конструкции, есть еще одна вещь, которую я не понимаю в дереве суффиксов. Поскольку ребра в дереве суффиксов — это просто пара целых чисел (правильно?), определяющих начальную и конечную позицию подстроки, то, если я хочу найти строку x в этом дереве суффиксов, как мне это сделать? Это? Разыменуйте эти целые числа в дереве суффиксов, затем сравните их один за другим с x? Не может быть так.