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