Longest Palindrome in a String formed by concatenating its prefix and suffix | C ++ program to find the longest palindrome in a string formed by concatenating its prefix and suffix ; Function to check whether the string is a palindrome ; Reverse the string to compare with the original string ; Check if both are same ; Function to find the longest palindrome in a string formed by concatenating its prefix and suffix ; Length of the string ; Finding the length upto which the suffix and prefix forms a palindrome together ; Check whether the string has prefix and suffix substrings which are palindromes . ; Removing the suffix and prefix substrings which already forms a palindrome and storing them in separate strings ; Check all prefix substrings in the remaining string str ; Check if the prefix substring is a palindrome ; If the prefix substring is a palindrome then check if it is of maximum length so far ; Check all the suffix substrings in the remaining string str ; Check if the suffix substring is a palindrome ; If the suffix substring is a palindrome then check if it is of maximum length so far ; Combining all the thee parts of the answer ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isPalindrome ( string r ) { string p = r ; reverse ( p . begin ( ) , p . end ( ) ) ; return ( r == p ) ; } string PrefixSuffixPalindrome ( string str ) { int n = str . size ( ) , len = 0 ; for ( int i = 0 ; i < n / 2 ; i ++ ) { if ( str [ i ] != str [ n - i - 1 ] ) { len = i ; break ; } } string prefix = " " , suffix = " " ; string midPal = " " ; prefix = str . substr ( 0 , len ) ; suffix = str . substr ( n - len ) ; str = str . substr ( len , n - 2 * len ) ; for ( int i = 1 ; i <= str . size ( ) ; i ++ ) { string y = str . substr ( 0 , i ) ; if ( isPalindrome ( y ) ) { if ( midPal . size ( ) < y . size ( ) ) { midPal = y ; } } } for ( int i = 1 ; i <= str . size ( ) ; i ++ ) { string y = str . substr ( str . size ( ) - i ) ; if ( isPalindrome ( y ) ) { if ( midPal . size ( ) < y . size ( ) ) { midPal = y ; } } } string answer = prefix + midPal + suffix ; return answer ; } int main ( ) { string str = " abcdfdcecba " ; cout << PrefixSuffixPalindrome ( str ) << " STRNEWLINE " ; return 0 ; }