Note that if we have some power S^(2k) where k>1, we can decompose that into k copies of S^2 without decreasing the total.
Thus the problem is equivalent to: give 2n where n is the largest number of squares we can decompose the string into. If we can find all of the squares, then we can use DP to solve. On the other hand we have to be careful not to end up with an O(n^2) algorithm. Sent from my iPad On 12 May 2013, at 22:21, Piyush Raman <[email protected]> wrote: > I have been trying to solve this problem- http://www.spoj.com/problems/ABA12B/ > but am having difficulty in finding any efficient approach. Kindly help. > Can we use suffix arrays to solve this problem? > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/32fbfd07-bf15-4456-8cdb-56ce603a9375%40googlegroups.com?hl=en. > For more options, visit https://groups.google.com/groups/opt_out. > > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
