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
def longestSubsequence ( X , Y ) : NEW_LINE INDENT n = len ( X ) NEW_LINE m = len ( Y ) NEW_LINE mat = [ [ 0 for i in range ( m + 1 ) ] for j in range ( n + 1 ) ] NEW_LINE for i in range ( 0 , n + 1 ) : NEW_LINE INDENT for j in range ( 0 , m + 1 ) : NEW_LINE INDENT if ( i == 0 or j == 0 ) : NEW_LINE INDENT mat [ i ] [ j ] = 0 NEW_LINE DEDENT DEDENT DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , m + 1 ) : NEW_LINE INDENT if ( X [ i - 1 ] == Y [ j - 1 ] ) : NEW_LINE INDENT mat [ i ] [ j ] = 1 + mat [ i - 1 ] [ j - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT mat [ i ] [ j ] = mat [ i - 1 ] [ j ] NEW_LINE DEDENT DEDENT DEDENT len1 = 0 NEW_LINE col = 0 NEW_LINE for i in range ( 0 , m + 1 ) : NEW_LINE INDENT if ( mat [ n ] [ i ] > len1 ) : NEW_LINE INDENT len1 = mat [ n ] [ i ] NEW_LINE col = i NEW_LINE DEDENT DEDENT res = " " NEW_LINE i = n NEW_LINE j = col NEW_LINE while ( len1 > 0 ) : NEW_LINE INDENT if ( X [ i - 1 ] == Y [ j - 1 ] ) : NEW_LINE INDENT res = X [ i - 1 ] + res NEW_LINE i -= 1 NEW_LINE j -= 1 NEW_LINE len1 -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT i -= 1 NEW_LINE DEDENT DEDENT return res NEW_LINE DEDENT X = " ABCD " NEW_LINE Y = " ACDBDCD " NEW_LINE print ( longestSubsequence ( X , Y ) ) NEW_LINE