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

Обсуждение задачи 1706. Шифровка 2

Algorithm
Послано Tbilisi SU: Giorgi , Nadira , [Kakia] 6 апр 2009 14:37
how to solve this problem?
construct suffix tree for N times and then LCP or there is easier and faster way?
Re: Algorithm
Послано UdSU: Abizyaev, Bikov, Urbanovich 6 апр 2009 20:01
Construct suffix tree for each window. Sliding should be at most O(k).
Re: Algorithm
Послано N.M.Hieu ( DHSP ) 7 апр 2009 17:31
Try DP.
It's easier to code (+ short) and run much faster than using suffix tree although having the same complexity O(N*K).
Re: Algorithm
Послано Anton [SUrSU] 7 апр 2009 18:52
Could you please decribe me DP solution?
Re: Algorithm
Послано Гладких Максим 9 апр 2009 07:42
Stupid implementation of the hash-table is even easier to code and much easier to invent.
Re: Algorithm
Послано UdSU: Abizyaev, Bikov, Urbanovich 9 апр 2009 21:42
Coding is not difficult at all. It seems to be more interesting that there exists O(n + k) solution, isn't it?
Re: Algorithm
Послано Гладких Максим 10 апр 2009 20:31
O(n=4000 + k=1000) would work 0.001ms ;)
Re: Algorithm
Послано UdSU: Abizyaev, Bikov, Urbanovich 11 апр 2009 00:39
Hardly. O(n + k) may have arbitrary coefficient. And no one said that solution had been submitted at Timus.
Re: Algorithm
Послано maksay 19 июн 2009 22:27
AC in 0.109 using only Z-function (also called suffix-function)
Re: Algorithm
Послано SkidanovAlex 14 ноя 2009 06:48
Z-function is not necessary here, KMP is enough.
0.14 using KMP.
Re: Algorithm
Послано Ivanov Alexander (HSE Mozgless Eagles) 24 июл 2011 21:43
And what is the "stupid implementation of the hash-table"?
My stupid implementation got TL.
Re: Algorithm
Послано Ivanov Alexander (HSE Mozgless Eagles) 25 июл 2011 00:41
Could you explain how to use KMP here?
Re: Algorithm
Послано bsu.mmf.team 25 июл 2011 18:58
Re: Algorithm
Послано adamant 22 фев 2014 14:46


Edited by author 22.02.2014 15:24
Re: Algorithm
Послано Mahilewets 12 июл 2017 12:19
Probably DP solution is actually a suffix automation.
In suffix automation,  we have the following DP.
Let X is some state of DAWG.
Let DP[X] =1+sum(DP[Y]){there is an edge from X to Y in DAWG}.
Then the answer is DP [ROOT] - 1. (Because empty substring not counts)

Edited by author 12.07.2017 12:20