Longest palindromic string possible after removal of a substring | Function to find the longest palindrome from the start of the string using KMP match ; Append S ( reverse of C ) to C ; Use KMP algorithm ; Function to return longest palindromic string possible from the given string after removal of any substring ; Initialize three strings A , B AND F ; Loop to find longest substrings from both ends which are reverse of each other ; Proceed to third step of our approach ; Remove the substrings A and B ; Find the longest palindromic substring from beginning of C ; Find the longest palindromic substring from end of C ; Store the maximum of D and E in F ; Find the final answer ; Driver code
def findPalindrome ( C ) : NEW_LINE INDENT S = C [ : : - 1 ] NEW_LINE C = C [ : ] + ' & ' + S NEW_LINE n = len ( C ) NEW_LINE longestPalindrome = [ 0 for i in range ( n ) ] NEW_LINE longestPalindrome [ 0 ] = 0 NEW_LINE ll = 0 NEW_LINE i = 1 NEW_LINE while ( i < n ) : NEW_LINE INDENT if ( C [ i ] == C [ ll ] ) : NEW_LINE INDENT ll += 1 NEW_LINE longestPalindrome [ i ] = ll NEW_LINE i += 1 NEW_LINE DEDENT else : NEW_LINE INDENT if ( ll != 0 ) : NEW_LINE INDENT ll = longestPalindrome [ ll - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT longestPalindrome [ i ] = 0 NEW_LINE i += 1 NEW_LINE DEDENT DEDENT DEDENT ans = C [ 0 : longestPalindrome [ n - 1 ] ] NEW_LINE return ans NEW_LINE DEDENT def findAns ( s ) : NEW_LINE INDENT A = " " NEW_LINE B = " " NEW_LINE F = " " NEW_LINE i = 0 NEW_LINE j = len ( s ) - 1 NEW_LINE ll = len ( s ) NEW_LINE while ( i < j and s [ i ] == s [ j ] ) : NEW_LINE INDENT i = i + 1 NEW_LINE j = j - 1 NEW_LINE DEDENT if ( i > 0 ) : NEW_LINE INDENT A = s [ 0 : i ] NEW_LINE B = s [ ll - i : ll ] NEW_LINE DEDENT if ( ll > 2 * i ) : NEW_LINE INDENT C = s [ i : i + ( len ( s ) - 2 * i ) ] NEW_LINE D = findPalindrome ( C ) NEW_LINE C = C [ : : - 1 ] NEW_LINE E = findPalindrome ( C ) NEW_LINE if ( len ( D ) > len ( E ) ) : NEW_LINE INDENT F = D NEW_LINE DEDENT else : NEW_LINE INDENT F = E NEW_LINE DEDENT DEDENT answer = A + F + B NEW_LINE return answer NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT str = " abcdefghiedcba " NEW_LINE print ( findAns ( str ) ) NEW_LINE DEDENT