algorithm - ukkonen - suffix tree wiki



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

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

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

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

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

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

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





suffix-tree