human
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"
How can the above be solved in Python?
 Give me a code to print Longest Palindromic Subsequence and the other steps required?
assistant
#Here is code to print Longest Palindromic Subsequence and the other steps required.
 def lcs_ ( X , Y ) :
	m = len ( X )
	n = len ( Y )
	L = [ [ 0 ] * ( n + 1 ) ] * ( m + 1 )
	for i in range ( n + 1 ) :
		for j in range ( n + 1 ) :
			if ( i == 0 or j == 0 ) :
				L [ i ] [ j ] = 0 ;
			elif ( X [ i - 1 ] == Y [ j - 1 ] ) :
				L [ i ] [ j ] = L [ i - 1 ] [ j - 1 ] + 1 ;
			else :
				L [ i ] [ j ] = max ( L [ i - 1 ] [ j ] , L [ i ] [ j - 1 ] ) ;
	index = L [ m ] [ n ] ;
	lcs = [ "   " ] * ( index + 1 )
	i , j = m , n
	while ( i > 0 and j > 0 ) :
		if ( X [ i - 1 ] == Y [ j - 1 ] ) :
			lcs [ index - 1 ] = X [ i - 1 ]
			i -= 1
			j -= 1
			index -= 1
		elif ( L [ i - 1 ] [ j ] > L [ i ] [ j - 1 ] ) :
			i -= 1
		else :
			j -= 1
	ans = " "
	for x in range ( len ( lcs ) ) :
		ans += lcs [ x ]
	return ans
def longestPalSubseq ( string ) :
	rev = string [ : : - 1 ]
	return lcs_ ( string , rev )
if __name__ == " _ _ main _ _ " :
	string = " GEEKSFORGEEKS " ;
	print ( longestPalSubseq ( string ) )