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

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)

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

Re: O(N)

Your time is not so good after rejudge. :)

Re: O(N)

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)

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)

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

Re: O(N)

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

Re: O(N)

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