@@ -0,0 +1,1285 @@
+%22%22%22find the length of longest subsequence present in both of them.%0A A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.%0A Examples:%0ALCS for input Sequences %E2%80%9CABCDGH%E2%80%9D and %E2%80%9CAEDFHR%E2%80%9D is %E2%80%9CADH%E2%80%9D of length 3.%0ALCS for input Sequences %E2%80%9CAGGTAB%E2%80%9D and %E2%80%9CGXTXAYB%E2%80%9D is %E2%80%9CGTAB%E2%80%9D of length 4.%22%22%22%0A%0A%0Adef lcs(str1, str2):%0A    m = len(str1)%0A    n = len(str2)%0A%0A    matrix = %5B%5B0 for i in range(n+1)%5D for i in range(m+1)%5D%0A%0A    for i in range(1, m+1):%0A        for j in range(1, n+1):%0A%0A            if i == 0 or j == 0:%0A                matrix%5Bi%5D%5Bj%5D = 0%0A%0A            elif str1%5Bi-1%5D == str2%5Bj-1%5D:%0A                matrix%5Bi%5D%5Bj%5D = 1 + matrix%5Bi-1%5D%5Bj-1%5D%0A%0A            else:%0A                matrix%5Bi%5D%5Bj%5D = max(matrix%5Bi-1%5D%5Bj%5D, matrix%5Bi%5D%5Bj-1%5D)%0A%0A    index = matrix%5Bm%5D%5Bn%5D%0A%0A    res = %5B%22%22%5D * index%0A    i = m%0A    j = n%0A%0A    while i %3E 0 and j %3E 0:%0A        if str1%5Bi-1%5D == str2%5Bj-1%5D:%0A            res%5Bindex-1%5D = str1%5Bi-1%5D%0A            i -= 1%0A            j -= 1%0A            index -= 1%0A%0A        elif matrix%5Bi-1%5D%5Bj%5D %3E matrix%5Bi%5D%5Bj-1%5D:%0A            i -= 1%0A        else:%0A            j -= 1%0A%0A    return res%0A%0A%0Aif __name__ == '__main__':%0A    X = %22AGGTAB%22%0A    Y = %22GXTXAYB%22%0A%0A    str = ''.join(lcs(X, Y))%0A%0A    print(%22Length of longest common subsequence is:%22, len(str),%22%5CnAnd the subsequence is:%22, str)

Given two sequences, print the longest subsequence present in them