ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1297. Palindrome

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.

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)?