|
|
back to boardthis 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 O(N) used hash function ;) How did you do that? Naive O( N ^ 2 ) = 0.015, 116 kb also this can be solved with Manacher's algorithm in O(N) =) also this can be solved with Manacher's algorithm in O(N) =) |
|
|
