Discussion @ 1706. Cipher Message 2 @ Timus Online Judge

Algorithm 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 UdSU: Abizyaev, Bikov, Urbanovich 6 Apr 2009 20:01

Construct suffix tree for each window. Sliding should be at most O(k).

Re: Algorithm 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 Anton [SUrSU] 7 Apr 2009 18:52

Could you please decribe me DP solution?

Re: Algorithm Гладких Максим 9 Apr 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 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 Гладких Максим 10 Apr 2009 20:31

O(n=4000 + k=1000) would work 0.001ms ;)

Re: Algorithm 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 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 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

Re: Algorithm maksay 19 Jun 2009 22:27

AC in 0.109 using only Z-function (also called suffix-function)

Re: Algorithm SkidanovAlex 14 Nov 2009 06:48

Z-function is not necessary here, KMP is enough.
0.14 using KMP.

Re: Algorithm Ivanov Alexander (HSE Mozgless Eagles) 25 Jul 2011 00:41

Could you explain how to use KMP here?

Re: Algorithm bsu.mmf.team 25 Jul 2011 18:58

Read this:
http://e-maxx.ru/algo/prefix_function

Re: Algorithm adamant 22 Feb 2014 14:46

Edited by author 22.02.2014 15:24

Discussion of Problem 1706. Cipher Message 2