Description: We have to find the longest possible substring of a string S which is a palindrome.

Example:
Input:

S: “a b k k b z y”

Output:

Longest palindrome substring: “bkkb”

Algorithm and Implementation:
We’ll solve this problem using Dynamic Programming.
We define:
ispal(m, n)=  {   1   , if the substring between indexes ‘m’ and ‘n’ is a palindrome
                         0,     otherwise
                        }
ispal(m,n)=  {1, if string[m]=string[n] and ispal(m+1,n-1)=1
                        0, otherwise           
                        }
 The longest possible palindrome substring would be when value of ‘n-m+1’ is maximum , where ispal(m,n)=1.
 
To solve the problem using dynamic programming, we create a matrix ispal(j,k) of size nXn where j:row no. and k: column no.
 
/*The following function finds the longest palidromic substring.*/
int longestPalidromeSubstring( char *str )
{
int n = strlen( str ); /*get length of input string*/
 
/*ispal[i][j] will be 1 if the substring str[i..j] is a palindrome.*/
int ispal[n][n];
memset( ispal, 0, sizeof( ispal) );
int max=1;/*stores maximum length*/
 
for( int i = 0; i < n; ++i )
  ispal[i][i] = 1;/*all substrings of length 1 are palindromes*/
/*check for sub-string of length 2.*/
 
int start = 0;
for( int i = 0; i < n-1; ++i )
{
 if( str[i] == str[i+1] )
{
 ispal[i][i+1] = 1;
 start = i;
 max= 2;
}
}
 
/* Check for lengths greater than 2 where ‘k’ is the length of substring*/
for( int k = 3; k <= n; ++k )
{
for( int i = 0; i < n - k + 1 ; ++i )
{
 int j = i + k - 1;/*’j’ is ending index of substring*/
 
 /*now consider the substring str[i…j]*/ 
/*checking for sub-string from ith index to jth index only if str[i+1…j-1] is a palindrome*/
 if( ispal[i+1][j-1] && str[i] == str[j] )
{
  ispal[i][j] = 1;
  if( k > max)
    {
       start = i;
       max = k;
      }
 }
 }
 }
/*PRINT LONGEST PALINDROME SUBSTRING-> str[start….start+max-1] */
return max; /*return length of longest palindrome substring*/
}
 
Time Complexity:
O(n*n)
Go to top