|
|
back to boardЯ построил дерево, программа работает правильно, но требует около 90МБ памяти. Как можно сократить количество используемой на дерево памяти? Попробуй взять другой алгоритм.
Префиксные массивы проходят по времени. there exist simple O(N^2) DP (N^2 memory)
but on the contest i have solve it in O(N^2) using hash
(O(N) memory) How to DP in this problem? Что за дерево Вы строите? Я строил суффиксное дерево, представляя ребра как два целых числа - начало и длины. Всего я поставил ограничение на массив вершин, используемых деревом, 40000 вершин (что в память уложится по-любому - в вершине хранится начало текста, длина текста, и 26 указателей на потомков). Совет: дерево должно быть компактным, то есть не отводить по вершине на символ, а только на разветвления, в этом случае дерево требует O(m) вершин, где m - длина текста. Проходит наивный алгоритм построения за O(N^2). |
|
|
