Re: Timus 1590 hash
У меня, например, хеши ТЛяться:) Возможно они кривые, но всё же... 
Разве тебе не интересны ещё способы решить такую тривиальную задачу?
Re: Timus 1590 hash
Acmefan пишет:
e-maxx пишет:А, ну кстати по решению с бором - не всё так плохо, можно строить сжатый бор - за квадрат его строить не так уж и сложно
а смысл тогда, если хешами тоже за квадрат решаем с меньшим напрягом
Думаю, всё же хеши с хешсетами сложнее запихать, чем "чистый" квадрат бора
Re: Timus 1590 hash
coder.ua пишет:
У меня, например, хеши ТЛяться:) Возможно они кривые, но всё же...
Способы интересны. Но каждой грядке - свой инструмент.
e-maxx пишет:
Думаю, всё же хеши с хешсетами сложнее запихать, чем "чистый" квадрат бора
Сложнее в плане времени выполнения, или времени написания?
Т.е. если и хеши и такой бор имеют одинаковую асимптотику, то на контесте нужно минимизировать время написания.
И мне кажется, что хеши пишутся намного быстрее бора.
Re: Timus 1590 hash
Пишутся хеши, конечно, побыстрей - я сам большой их любитель
Я говорил про время выполнения - собсно, этот топик отсюда и возник, что решение-то за n^2 log n, или за n^2, но с константой хешсета.
Re: Timus 1590 hash
KADR пишет:
coder.ua пишет:Добавление у меня такое же, но я кажется понял в чём ошибка у меня: ты наверное перебираешь все подстроки по длине сначала, а потом очищаешь список. Я же всё кидал в один список...:/
Большое спасибо за помощь!Да, я после проверки очередной длины очищаю хешсет.
А как ты очищаешь хэшсет? У меня вроде бы ТЛ...
Re: Timus 1590 hash
Я хеширую по модулю 1027. Чтобы очистить хешсет посто заполняю массив last минус единицами (см. код добавления на предыдущей странице).
Re: Timus 1590 hash
Как написать динамику http://e-maxx.ru/algo/suffix_automata#16?
Re: Timus 1590 hash
Hack-Yer пишет:
Как написать динамику http://e-maxx.ru/algo/suffix_automata#16?
Количество различных подстрок? Ну прямо по той формуле, что в статье написана: значение динамики для какого-либо состояния равно сумме динамик по всем рёбрам из этого состояния и плюс один.