Тут спрашивают, бывают ли суфф деревья с O(1) в худшем случае на добавление одного символа в конец строки. Смысл, конечно, в том, чтобы суфф дерево сделать персистентным :D
Год назад таких ещё не было
http://compsciclub.ru/courses/suffixtrees
Внутри ссылка на лучший на тот момент результат, O(loglogn):
http://www.sciencedirect.com/science/article/pii/S1570866712001062
А вот про суфф автоматы я не знаю.... кто у нас лучше всех знает автоматы?) #ИТМО ? Хотя бы за полилог наверняка же можно... P.S. Link-cut не предлагать, там амортизированное время.
Год назад таких ещё не было
http://compsciclub.ru/courses/suffixtrees
Внутри ссылка на лучший на тот момент результат, O(loglogn):
http://www.sciencedirect.com/science/article/pii/S1570866712001062
А вот про суфф автоматы я не знаю.... кто у нас лучше всех знает автоматы?) #ИТМО ? Хотя бы за полилог наверняка же можно... P.S. Link-cut не предлагать, там амортизированное время.
Here they ask whether there are suffix trees with O (1) in the worst case of adding one character to the end of the line. The point, of course, is to make the suffix tree persistent: D
A year ago, there were no such
http://compsciclub.ru/courses/suffixtrees
Inside the link to the best result at that time, O (loglogn):
http://www.sciencedirect.com/science/article/pii/S1570866712001062
But I don’t know about the suffix automata .... who among us knows the automata best of all?) ITMO? At least for a polylog it’s certainly possible ... P.S. Link-cut does not offer, there is amortized time.
A year ago, there were no such
http://compsciclub.ru/courses/suffixtrees
Inside the link to the best result at that time, O (loglogn):
http://www.sciencedirect.com/science/article/pii/S1570866712001062
But I don’t know about the suffix automata .... who among us knows the automata best of all?) ITMO? At least for a polylog it’s certainly possible ... P.S. Link-cut does not offer, there is amortized time.
У записи 1 лайков,
0 репостов.
0 репостов.
Эту запись оставил(а) на своей стене Sergey Kopeliovich
