Обсуждение @ 1297. Палиндромы @ Timus Online Judge

O(N)

Послано sloboz 13 апр 2004 05:57

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

Re: O(N)

Послано Gheorghe Stefan 15 апр 2004 05:15

you maniac!

Re: O(N)

Послано mytest 26 апр 2004 22:03

What is the test #7? )

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

Послано Dilyan 2 июл 2004 15:29

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

Re: O(N)

Послано Tihon Sergey 10 янв 2007 02:29

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

Re: O(N)

Послано Sandro (USU) 10 янв 2007 16:18

Your time is not so good after rejudge. :)

Re: O(N)

Послано Shadow of Death 17 окт 2007 23:16

Just O(2N)
Use Prefix Function!

Re: O(N)

Послано kima 21 ноя 2009 02:42

O(N) used hash function ;)

Re: O(N)

Послано Artem Khizha [DNU] 4 авг 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)

Послано mabodx 7 сен 2010 06:59

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

Re: O(N)

Послано Anuar 15 дек 2011 09:54

How did you do that?

Re: O(N)

Послано Soucup Adrian 27 июл 2012 19:05

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

Re: O(N)

Послано lichtgestalt2710 13 фев 2014 06:41

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

Re: O(N)

Послано lichtgestalt2710 13 фев 2014 06:41

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

Re: O(N)

Послано OIdiot 14 авг 2014 19:04

O(NlogN)?

Обсуждение задачи 1297. Палиндромы