The Longest Palindrome problem

See here for a linear solution.

Another blog for linear solution.

Another linear solution is to use suffix tree.