Discussion @ 1297. Palindrome @ Timus Online Judge

O(N)

Posted by sloboz 13 Apr 2004 05:57

this can be done very cool in O(N) with Suffix Trees. Try it!

Re: O(N)

Posted by Gheorghe Stefan 15 Apr 2004 05:15

you maniac!

Re: O(N)

Posted by mytest 26 Apr 2004 22:03

What is the test #7? )

please tell me how do to it in O(n)

Posted by Dilyan 2 Jul 2004 15:29

write me to dpdokov@yahoo.com
or post you idia here
?!?!?!?!?!?!?!?!

Re: O(N)

Posted by Tihon Sergey 10 Jan 2007 02:29

Solution O(N^3) with some optimization AC 0.001

Re: O(N)

Posted by Sandro (USU) 10 Jan 2007 16:18

Your time is not so good after rejudge. :)

Re: O(N)

Posted by Shadow of Death 17 Oct 2007 23:16

Just O(2N)
Use Prefix Function!

Re: O(N)

Posted by kima 21 Nov 2009 02:42

O(N) used hash function ;)

Re: O(N)

Posted by Artem Khizha [DNU] 4 Aug 2010 23:00

After all, I solved the problem by DP in O(N), counting the number of palindromes, though it is rather hard.

2 Shadow of Death:
I'm very interested in solution with prefix-function, would you be so kind to tell more about it? I'm a newbie in string-algorithms, but hope to learn them better.

Re: O(N)

Posted by mabodx 7 Sep 2010 06:59

if you have learned suffix arrays you can use that to solve these problem . it's not difficult

Re: O(N)

Posted by Anuar 15 Dec 2011 09:54

How did you do that?

Re: O(N)

Posted by Soucup Adrian 27 Jul 2012 19:05

Naive O( N ^ 2 ) = 0.015, 116 kb

Re: O(N)

Posted by lichtgestalt2710 13 Feb 2014 06:41

also this can be solved with Manacher's algorithm in O(N) =)

Re: O(N)

Posted by lichtgestalt2710 13 Feb 2014 06:41

also this can be solved with Manacher's algorithm in O(N) =)

Re: O(N)

Posted by OIdiot 14 Aug 2014 19:04

O(NlogN)?

Discussion of Problem 1297. Palindrome