Longest Palindrome Substring.

Problem Statement : Given a string, find longest palindrome substring in it.

Solution 1 : We have n*(n+1)/2 numbers of substrings present in a string of length n. Checking a string whether it’s palindrome or not takes O(n) time. So, As a whole, it will take O(n^3) time.

Solution 2 : Solution 1 can be improved by using Dynamic Programming approach. The recurrence relation can be easily written down to :

L(i , j) = 1, If the string from A[i……j] is palindrome.

L(i , i+1) = 1, If A[i] = A[i+1]

L(i , j) = L(i+1 , j-1), If A[i] = A[j]

The filling of these entries will take O(n^2) time.

Manacher’s Algorithm : This algorithm will take O(n) time to detect the longest palindrome substring.

I will illustrate it with an example :

let A = abaaba

We will insert ‘#’ between every character,  so A will become

A = # a # b # a # a # b # a #

For each character, We will count the length of characters which are same on either side. (Say, in array P)

So, A = # a # b # a # a # b # a #

P = 0 1 0 3 0 1 6 1 0 3 0 1 0 

It can be seen that array P is symmetric around value 6. We can reduce the counting of right side of the central element of a palindrome.

So, In the code, we will set 2 variables C & R. (Center and Right)

On every index, we will try to expand the length of pallindrome if current index is set to be the center.

If length of palindrome from current index is beyond ‘R’ variable, then we will update ‘C’ and ‘R’.

code : http://pastebin.com/Ex2cYGkH

Further readings: http://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-1/

http://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-2/

http://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-3-2/

http://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-4/

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

Advertisements