Algorithm for finding longest palindrome substring

Let us just think about some way for finding palindromic sub string. My initial idea was to do a brute-force search. In that, we take each character and check the longest palindromic string that can be made by considering that character as the centre. If that character and next character are the same, then take both characters as centre and check for palindromes.

Example:   if we check for  aabbababb

take first character a the longest palindrome with first a is a itself, as there are no elements to its left.also we can see that second letter is also a. But we cannot find a palindromic string with length more than 2 with aa as centre. Now  we look at b. there are different characters in the immediate left and immediate right of that b. But, we see that character next to b is b itself. So, we take bb as centre and check for its immediate left and immediate right characters. Both are a. So,we get a palindrome with length 4 starting from index 1 to 4(assuming string is stored from starting index 0). Now again, if we check the left and right characters of abba, we find that both are different. So we can check the next character and so on.

   Now, we can see that within a palindromic string, if a palindrome occurs, it will be symmetric on both sides of the centre element. This property helps us to reduce the number of iterations to be performed on the palindromic strings.This is exploited in the Manacher’s algorithm which finds the longest palindromic sub string in O(n) time.  One of the best explanations for this can be seen here.

http://articles.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s