Понимание алгоритма Укконена для суффиксных деревьев
Я делаю некоторую работу с алгоритмом Укконена для построения суффиксных деревьев, но я не понимаю некоторые части объяснения автора для его линейной сложности времени.
Я выучил алгоритм и закодировал его, но статья, которую я использую в качестве основного источника информации (ссылка ниже), в некотором роде сбивает с толку, поэтому мне не совсем понятно, почему алгоритм является линейным.
Любая помощь? Благодарю.
Ссылка на статью Укконена: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
1 ответ
Решение
Найдите копию учебника по строковым алгоритмам Гусфилда. Это лучшая экспозиция конструкции дерева суффиксов, которую я видел. Линейность является неожиданным следствием ряда оптимизаций алгоритма высокого уровня.