На этот вопрос уже есть ответ здесь:

Я делаю некоторую работу с алгоритмом Укконена для построения суффиксных деревьев, но я не понимаю некоторые части объяснения автора для его линейной сложности времени.

Я выучил алгоритм и закодировал его, но статья, которую я использую в качестве основного источника информации (см. Ниже), в некотором роде сбивает с толку, поэтому мне не совсем понятно, почему алгоритм является линейным.

Любая помощь? Благодарю.

Ссылка на статью Укконена:http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf