human
Find the longest subsequence of a string that is a substring of another string | Function to find the longest subsequence that matches with the substring of other string.
Stores the lengths of strings X and Y.
Create a matrix.
Initialize the matrix.
Fill all the remaining rows.
If the characters are equal.
If not equal , then just move to next in subsequence string.
Find maximum length of the longest subsequence matching substring of other string.
Iterate through the last row of matrix.
Store the required string.
Backtrack from the cell.
If equal , then add the character to res string.
Return the required string.
Driver code"
How can the above be solved in Python?
assistant
#Here is code to find the longest subsequence of a string that is a substring of another string and the other steps required.
 def longestSubsequence ( X , Y ) :
	n = len ( X )
	m = len ( Y )
	mat = [ [ 0 for i in range ( m + 1 ) ] for j in range ( n + 1 ) ]
	for i in range ( 0 , n + 1 ) :
		for j in range ( 0 , m + 1 ) :
			if ( i == 0 or j == 0 ) :
				mat [ i ] [ j ] = 0
	for i in range ( 1 , n + 1 ) :
		for j in range ( 1 , m + 1 ) :
			if ( X [ i - 1 ] == Y [ j - 1 ] ) :
				mat [ i ] [ j ] = 1 + mat [ i - 1 ] [ j - 1 ]
			else :
				mat [ i ] [ j ] = mat [ i - 1 ] [ j ]
	len1 = 0
	col = 0
	for i in range ( 0 , m + 1 ) :
		if ( mat [ n ] [ i ] > len1 ) :
			len1 = mat [ n ] [ i ]
			col = i
	res = " "
	i = n
	j = col
	while ( len1 > 0 ) :
		if ( X [ i - 1 ] == Y [ j - 1 ] ) :
			res = X [ i - 1 ] + res
			i -= 1
			j -= 1
			len1 -= 1
		else :
			i -= 1
	return res
X = " ABCD "
Y = " ACDBDCD "
print ( longestSubsequence ( X , Y ) )