Longest Palindromic Substring

Given a strings, find the longest palindromic substring ins. You may assume that the maximum length ofsis 1000.

Example:

Input:
 "babad"


Output:
 "bab"


Note:
 "aba" is also a valid answer.

Example:

Input:
 "cbbd"


Output:
 "bb"

Solution

Assume the string S = "banana". Begin by building the suffix tree, for S + R, where R is the reverse of S.

S = b a n a n a $ a n a n a b #
I = 1 2 3 4 5 6 7 8 9 0 1 2 3 4

Finally, return the path label along the LCS.

Why this works

This works exactly for the same reasons justified in the previous application. Since a palindrome is the same both backwards and forwards, its common shared occurrence will remain the same when the pattern is reversed. Then the properties of the LCS remain the same as before.