Longest palindromic string formed by concatenation of prefix and suffix of a string | 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
def kmp ( s ) : NEW_LINE INDENT lps = [ 0 ] * ( len ( s ) ) NEW_LINE for i in range ( 1 , len ( s ) ) : NEW_LINE INDENT previous_index = lps [ i - 1 ] NEW_LINE while ( previous_index > 0 and s [ i ] != s [ previous_index ] ) : NEW_LINE INDENT previous_index = lps [ previous_index - 1 ] NEW_LINE DEDENT lps [ i ] = previous_index NEW_LINE if ( s [ i ] == s [ previous_index ] ) : NEW_LINE INDENT lps [ i ] += 1 NEW_LINE DEDENT DEDENT return lps [ - 1 ] NEW_LINE DEDENT def remainingStringLongestPallindrome ( s ) : NEW_LINE INDENT t = s + " ? " NEW_LINE s = s [ : : - 1 ] NEW_LINE t += s NEW_LINE return kmp ( t ) NEW_LINE DEDENT def longestPrefixSuffixPallindrome ( s ) : NEW_LINE INDENT length = 0 NEW_LINE n = len ( s ) NEW_LINE i = 0 NEW_LINE j = n - 1 NEW_LINE while i < j : NEW_LINE INDENT if ( s [ i ] != s [ j ] ) : NEW_LINE INDENT break NEW_LINE DEDENT i += 1 NEW_LINE j -= 1 NEW_LINE length += 1 NEW_LINE DEDENT ans = s [ 0 : length ] NEW_LINE remaining = s [ length : length + ( n - ( 2 * length ) ) ] NEW_LINE if ( len ( remaining ) ) : NEW_LINE INDENT longest_prefix = remainingStringLongestPallindrome ( remaining ) ; NEW_LINE remaining = remaining [ : : - 1 ] NEW_LINE longest_suffix = remainingStringLongestPallindrome ( remaining ) ; NEW_LINE if ( longest_prefix > longest_suffix ) : NEW_LINE INDENT remaining = remaining [ : : - 1 ] NEW_LINE ans += remaining [ 0 : longest_prefix ] NEW_LINE DEDENT else : NEW_LINE INDENT ans += remaining [ 0 : longest_suffix ] NEW_LINE DEDENT DEDENT ans += s [ n - length : n ] NEW_LINE return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT st = " rombobinnimor " NEW_LINE print ( longestPrefixSuffixPallindrome ( st ) ) NEW_LINE DEDENT