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