|
|
back to boardMy idea for O(n) but wrong for test #5 Posted by AnhDQ 30 Apr 2008 17:57 F[i]: the longest Palindrom ended at St[i]
Cont[i]: the number of continue same characters with St[i], ended at St[i]
if St[i] = St[i - F[i - 1] - 1] then
F[i] = F[i - 1] + 2
else
if St[i] = St[i - 1] then
F[i] = Cont[i];
The result is Max(F)
What's wrong with it ??? Re: My idea for O(n) but wrong for test #5 aabbbaabbb
it is wrong algorithm Re: My idea for O(n) but wrong for test #5 The only O(n) Algotithm is suffix tree+LCA or Suffix array + +-1RMQ+LCA+Catersian Tree F[i]: the longest Palindrom ended at St[i]
Cont[i]: the number of continue same characters with St[i], ended at St[i]
if St[i] = St[i - F[i - 1] - 1] then
F[i] = F[i - 1] + 2
else
if St[i] = St[i - 1] then
F[i] = Cont[i];
The result is Max(F)
What's wrong with it ??? Re: My idea for O(n) but wrong for test #5 That's wrong! There's another O(n) algorithm. It's called Manacher's algorithm. Re: My idea for O(n) but wrong for test #5
Edited by author 09.10.2011 02:10 |
|
|
