ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1590. Шифр Бэкона

About the solving approach(+)
Послано SPIRiT 29 окт 2007 21:43
I know that suffix trees can be used for such problem. How about using a large hash table for storing codes of substrings that we already have? Anyone got AC in that way?
Re: About the solving approach(+)
Послано svr 29 окт 2007 22:16
I trying during a long time O(n) suffix tree of Ekkonen
but could'n catch all details. I think that you
question has the same nature. If you think about
yourself as good coder you should catch O(n) suffix tree.
Re: About the solving approach(+)
Послано Vedernikoff Sergey 30 окт 2007 17:40
I tried double-hash of about 30000 elements each but WA. Nevertheless, some people claim the problem may be solved with hash.
Re: About the solving approach(+)
Послано Lomir 13 ноя 2007 04:25
How do you calculate hash for n^2 substrings?
I calculate hash seperately for each lenth os substring by:
hashcode = prime^n*c1 + prime^(n-1)*c2 + prime^(n-2)*c1...

string movement is by 1 char:
newhashcode = (oldhashcode - prime^n*removedchar)*prime + prime*addedchar

This gets TLE 3.
Re: About the solving approach(+)
Послано Brainfuck 16 июл 2009 16:31
I use 'poganyi hash'. And it works very good. Yeah, baby!
Re: About the solving approach(+)
Послано SPIRiT 6 авг 2009 00:46
Finally managed to implement the Ukkonen algo correctly - worked from the first try and is much faster now, than with O(N^2) implementation. Here is my status board to examine:

 http://acm.timus.ru/status.aspx?space=1&num=1590&author=33910

Edited by author 06.08.2009 00:47

Edited by author 06.08.2009 00:48
Re: About the solving approach(+)
Послано Oracle[Lviv NU] 6 авг 2010 03:47
to Lomir: you should not use sorting. Without sorting this approach gives AC in 0.454 sec.
Re: About the solving approach(+)
Послано AterLux 7 сен 2010 20:51
Calculation of hash for each substring will take O(N^2). Then you need to check non-equal of string with same hash. For example for test 'aaaaaaaaaaaaa' (and longer) every substring of same length will have same hash code
Re: About the solving approach(+)
Послано Sushil Nath 24 июн 2011 01:17
Can it be done using ternary search tree