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

Question

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

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

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

Ссылка на бумаге Укконена: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

Answer 1

Найти копию Gusfield-х string algorithms textbook. У него есть лучшее изложение дерева суффикса, которое я видел. Линейность является неожиданным следствием ряда оптимизаций алгоритма высокого уровня.