CareerCup

Use suffix trees.

no don't use suffix trees. If you do explain how.

The basic idea is store (begin_pos, end_pos, length) as current longest palindrome seen so far and process char by char.
Also need to store the length of palindrome that ends just before the char to be processed, let's say leng_temp. When fetching next char:
Say the next char is s[i].
If i==end_pos+1 so I can check whether s[i]==s[begin_pos-1], if yes I can upgrade current longest palindrome to (begin_pos-1, end_pos+1, length+2).
If i!=end_pos+1 then we need to check whether s[i]==s[i-leng_temp-1] if positive the upgrade leng_temp, and if leng_temp>=length, update (begin_pos, end_pos, length) accordingly.
Note that I only write out some general idea, and there're some special cases need to be handle such as if the palindrome are composed with same char, then not only need to check begin_pos-1 also need to check begin_pos so on and so forth.
But basicly such algorithm should run in linear tim.e

its soo easy to do using O(n*2) algo

Reverse the string and looking for the longest common consecutive sequence of the reversed string and the original string. Time complexity is O(n).

I think this can be done in O(n) by simply process the string char by char from begin to end.