Алгоритм Укконена: от простого к сложному

Изучая курс Алгоритмы на строках столкнулся с задачей о построении суффиксного дерева. Перейдя по ссылке на дополнительные материалы наткнулся на рекомендацию "просмотреть этот замечательный комментарий на Stack Overflow". Изучив и реализовав по приведённому вольному описанию алгоритм Укконена решил поделиться переводом.

Ниже приводится попытка описания алгоритма Укконена; сначала показав, как он работает на простой строке (т.е. строка не содержит повторяющихся символов), постепенно расширяясь до полного алгоритма.

Несколько предварительных утверждений:

1. То, что мы строим - это в основе похоже на префиксное дерево. Это корневая вершина, чьи ребра выходят из неё в новые вершины, и последующие ребра выходят из них и так далее

2. Но, в отличие от префиксного дерева, метки ребра - не одиночные символы, у каждого ребра метка это пара чисел [от, до] - указатели на позиции в тексте. В таком случае, каждое ребро содержит строку произвольной длины, но занимает только O(1) памяти (два указателя)

Базовый принцип

Сначала автор хочет продемонстрировать как создать суффиксное дерево чрезвычайно простой строки, строки без повторяющихся символов: