Length of Longest Palindrome Substring | C ++ program for the above approach ; Function to find the length of the longest palindromic substring ; Length of string str ; Stores the dp states ; Initialise table [ ] [ ] as false ; All substrings of length 1 are palindromes ; Check for sub - string of length 2 ; If adjacent character are same ; Update table [ i ] [ i + 1 ] ; Check for lengths greater than 2 k is length of substring ; Fix the starting index ; Ending index of substring of length k ; Check for palindromic substring str [ i , j ] ; Mark true ; Update the maximum length ; Return length of LPS ; Driver Code ; Given string str ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; 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 ; } } } } return maxLength ; } int main ( ) { string str = " forgeeksskeegfor " ; cout << longestPalSubstr ( str ) ; return 0 ; }