Longest palindromic string formed by concatenation of prefix and suffix of a string | C ++ implementation of the above approach ; Function used to calculate the longest prefix which is also a suffix ; Traverse the string ; Update the lps size ; Returns size of lps ; Function to calculate the length of longest palindromic substring which is either a suffix or prefix ; Append a character to separate the string and reverse of the string ; Reverse the string ; Append the reversed string ; Function to find the Longest palindromic string formed from concatenation of prefix and suffix of a given string ; Calculating the length for which prefix is reverse of suffix ; Append prefix to the answer ; Store the remaining string ; If the remaining string is not empty that means that there can be a palindrome substring which can be added between the suffix & prefix ; Calculate the length of longest prefix palindromic substring ; Reverse the given string to find the longest palindromic suffix ; Calculate the length of longest prefix palindromic substring ; If the prefix palindrome is greater than the suffix palindrome ; Append the prefix to the answer ; If the suffix palindrome is greater than the prefix palindrome ; Append the suffix to the answer ; Finally append the suffix to the answer ; Return the answer string ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int kmp ( string s ) { vector < int > lps ( s . size ( ) , 0 ) ; for ( int i = 1 ; i < s . size ( ) ; i ++ ) { int previous_index = lps [ i - 1 ] ; while ( previous_index > 0 && s [ i ] != s [ previous_index ] ) { previous_index = lps [ previous_index - 1 ] ; } lps [ i ] = previous_index + ( s [ i ] == s [ previous_index ] ? 1 : 0 ) ; } return lps [ lps . size ( ) - 1 ] ; } int remainingStringLongestPallindrome ( string s ) { string t = s + " ? " ; reverse ( s . begin ( ) , s . end ( ) ) ; t += s ; return kmp ( t ) ; } string longestPrefixSuffixPallindrome ( string s ) { int length = 0 ; int n = s . size ( ) ; for ( int i = 0 , j = n - 1 ; i < j ; i ++ , j -- ) { if ( s [ i ] != s [ j ] ) { break ; } length ++ ; } string ans = s . substr ( 0 , length ) ; string remaining = s . substr ( length , ( n - ( 2 * length ) ) ) ; if ( remaining . size ( ) ) { int longest_prefix = remainingStringLongestPallindrome ( remaining ) ; reverse ( remaining . begin ( ) , remaining . end ( ) ) ; int longest_suffix = remainingStringLongestPallindrome ( remaining ) ; if ( longest_prefix > longest_suffix ) { reverse ( remaining . begin ( ) , remaining . end ( ) ) ; ans += remaining . substr ( 0 , longest_prefix ) ; } else { ans += remaining . substr ( 0 , longest_suffix ) ; } } ans += s . substr ( n - length , length ) ; return ans ; } int main ( ) { string str = " rombobinnimor " ; cout << longestPrefixSuffixPallindrome ( str ) << endl ; }