Print Longest Palindromic Subsequence | Returns LCS X and Y ; Following steps build L [ m + 1 ] [ n + 1 ] in bottom up fashion . Note that L [ i ] [ j ] contains length of LCS of X [ 0. . i - 1 ] and Y [ 0. . j - 1 ] ; Following code is used to print LCS ; Create a string length index + 1 and fill it with \ 0 ; Start from the right - most - bottom - most corner and one by one store characters in lcs [ ] ; If current character in X [ ] and Y are same , then current character is part of LCS ; Put current character in result ; reduce values of i , j and index ; If not same , then find the larger of two and go in the direction of larger value ; Returns longest palindromic subsequence of str ; Find reverse of str ; Return LCS of str and its reverse ; Driver Code
def lcs_ ( X , Y ) : NEW_LINE INDENT m = len ( X ) NEW_LINE n = len ( Y ) NEW_LINE L = [ [ 0 ] * ( n + 1 ) ] * ( m + 1 ) NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT for j in range ( n + 1 ) : NEW_LINE INDENT if ( i == 0 or j == 0 ) : NEW_LINE INDENT L [ i ] [ j ] = 0 ; NEW_LINE DEDENT elif ( X [ i - 1 ] == Y [ j - 1 ] ) : NEW_LINE INDENT L [ i ] [ j ] = L [ i - 1 ] [ j - 1 ] + 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT L [ i ] [ j ] = max ( L [ i - 1 ] [ j ] , L [ i ] [ j - 1 ] ) ; NEW_LINE DEDENT DEDENT DEDENT index = L [ m ] [ n ] ; NEW_LINE lcs = [ "   " ] * ( index + 1 ) NEW_LINE i , j = m , n NEW_LINE while ( i > 0 and j > 0 ) : NEW_LINE INDENT if ( X [ i - 1 ] == Y [ j - 1 ] ) : NEW_LINE INDENT lcs [ index - 1 ] = X [ i - 1 ] NEW_LINE i -= 1 NEW_LINE j -= 1 NEW_LINE index -= 1 NEW_LINE DEDENT elif ( L [ i - 1 ] [ j ] > L [ i ] [ j - 1 ] ) : NEW_LINE INDENT i -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT j -= 1 NEW_LINE DEDENT DEDENT ans = " " NEW_LINE for x in range ( len ( lcs ) ) : NEW_LINE INDENT ans += lcs [ x ] NEW_LINE DEDENT return ans NEW_LINE DEDENT def longestPalSubseq ( string ) : NEW_LINE INDENT rev = string [ : : - 1 ] NEW_LINE return lcs_ ( string , rev ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT string = " GEEKSFORGEEKS " ; NEW_LINE print ( longestPalSubseq ( string ) ) NEW_LINE DEDENT