|
|
вернуться в форумПоказать все сообщения Спрятать все сообщенияO(N) Macarie 13 апр 2004 05:57 this can be done very cool in O(N) with Suffix Trees. Try it! write me to dpdokov@yahoo.com
or post you idia here
?!?!?!?!?!?!?!?! Solution O(N^3) with some optimization AC 0.001 Your time is not so good after rejudge. :) Just O(2N)
Use Prefix Function! 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. if you have learned suffix arrays you can use that to solve these problem . it's not difficult Re: O(N) Nikolai Karpov 21 ноя 2009 02:42 O(N) used hash function ;) 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) =) |
|
|
