ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1706. Cipher Message 2

Algorithm
Posted by Tbilisi SU: Giorgi , Nadira , [Kakia] 6 Apr 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
Posted by UdSU: Abizyaev, Bikov, Urbanovich 6 Apr 2009 20:01
Construct suffix tree for each window. Sliding should be at most O(k).
Re: Algorithm
Posted by N.M.Hieu ( DHSP ) 7 Apr 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
Posted by Anton [SUrSU] 7 Apr 2009 18:52
Could you please decribe me DP solution?
Re: Algorithm
Posted by Гладких Максим 9 Apr 2009 07:42
Stupid implementation of the hash-table is even easier to code and much easier to invent.
Re: Algorithm
Posted by UdSU: Abizyaev, Bikov, Urbanovich 9 Apr 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
Posted by Гладких Максим 10 Apr 2009 20:31
O(n=4000 + k=1000) would work 0.001ms ;)
Re: Algorithm
Posted by UdSU: Abizyaev, Bikov, Urbanovich 11 Apr 2009 00:39
Hardly. O(n + k) may have arbitrary coefficient. And no one said that solution had been submitted at Timus.
Re: Algorithm
Posted by maksay 19 Jun 2009 22:27
AC in 0.109 using only Z-function (also called suffix-function)
Re: Algorithm
Posted by SkidanovAlex 14 Nov 2009 06:48
Z-function is not necessary here, KMP is enough.
0.14 using KMP.
Re: Algorithm
Posted by Ivanov Alexander (HSE Mozgless Eagles) 24 Jul 2011 21:43
And what is the "stupid implementation of the hash-table"?
My stupid implementation got TL.
Re: Algorithm
Posted by Ivanov Alexander (HSE Mozgless Eagles) 25 Jul 2011 00:41
Could you explain how to use KMP here?
Re: Algorithm
Posted by bsu.mmf.team 25 Jul 2011 18:58
Re: Algorithm
Posted by adamant 22 Feb 2014 14:46


Edited by author 22.02.2014 15:24
Re: Algorithm
Posted by Mahilewets 12 Jul 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