Longest Palindromic Substring | Set 1 | A C ++ dynamic programming solution for longest palindrome ; Function to print a substring str [ low . . high ] ; This function prints the longest palindrome substring It also returns the length of the longest palindrome ; get length of input string ; table [ i ] [ j ] will be false if substring str [ i . . j ] is not palindrome . Else table [ i ] [ j ] will be true ; All substrings of length 1 are palindromes ; check for sub - string of length 2. ; Check for lengths greater than 2. k is length of substring ; Fix the starting index ; Get the ending index of substring from starting index i and length k ; checking for sub - string from ith index to jth index iff str [ i + 1 ] to str [ j - 1 ] is a palindrome ; return length of LPS ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void printSubStr ( string str , int low , int high ) { for ( int i = low ; i <= high ; ++ i ) cout << str [ i ] ; } int longestPalSubstr ( string str ) { int n = str . size ( ) ; bool table [ n ] [ n ] ; memset ( table , 0 , sizeof ( table ) ) ; int maxLength = 1 ; for ( int i = 0 ; i < n ; ++ i ) table [ i ] [ i ] = true ; int start = 0 ; for ( int i = 0 ; i < n - 1 ; ++ i ) { if ( str [ i ] == str [ i + 1 ] ) { table [ i ] [ i + 1 ] = true ; start = i ; maxLength = 2 ; } } for ( int k = 3 ; k <= n ; ++ k ) { for ( int i = 0 ; i < n - k + 1 ; ++ i ) { int j = i + k - 1 ; if ( table [ i + 1 ] [ j - 1 ] && str [ i ] == str [ j ] ) { table [ i ] [ j ] = true ; if ( k > maxLength ) { start = i ; maxLength = k ; } } } } cout << " Longest ▁ palindrome ▁ substring ▁ is : ▁ " ; printSubStr ( str , start , start + maxLength - 1 ) ; return maxLength ; } int main ( ) { string str = " forgeeksskeegfor " ; cout << " Length is : " << longestPalSubstr ( str ) ; return 0 ; }