We used dynamic programming to solve the longest common subsequence (LCS) proble

Question

We used dynamic programming to solve the longest common subsequence (LCS) problem in

class. This algorithm needs to use a 2 dimensional array with size |x| * |y| given that x and y are two input

sequences. Now, modify the dynamic programming algorithm so that we only need to use a linear table

with size either |x| or |y|. Describe your idea (or modification) and then write your pseudocode.

Note: you don’t need to find the longest common subsequence between x and y. You only need to find the

size of an LCS

Explanation / Answer

Examples:
LCS for input Sequences X= ACBDAE and Y= AEBFER is “ABE” of length 3.
LCS for input Sequences X=AGCTAB and Y=GXTXAYB is “GTAB” of length 4.

We have discussed Longest Common Subsequence (LCS) problem.
Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n has 2n different possible subsequences.
The function discussed there was mainly to find the length of LCS. To find length of LCS, a 2D table L[][] was constructed. In this post, the function to construct and print LCS is discussed.

Following is detailed algorithm to print the LCS. It uses the same 2D table LEN[][].

1) Construct LEN[m+1][n+1] using the steps discussed in previous post.

2) The value LEN[m][n] contains length of LCS. Create a character array LCS[] of length equal to the length of LCS plus 1 (one extra to store ).

2) Traverse the 2D array starting from LEN[m][n]. Do following for every cell LEN[i][j]

a) If characters (in X and Y) corresponding to LEN[i][j] are same (Or X[i-1] == Y[j-1]), then include this character as part of LCS.

b) Else compare values of LEN[i-1][j] and LEN[i][j-1] and go in direction of greater value.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.