Assume X and Y are given strings, with |X| = |Y | = n, and assume that |LCS(X, Y

Question

Assume X and Y are given strings, with |X| = |Y | = n, and assume that |LCS(X, Y )| n10 (that is, all but at most 10 characters match). Suggest an O(n) time algorithm for finding LCS(X, Y ).

Extend your answer in the following way: Assume a parameter k < n is given. Show how you could find in time O(kn) whether |LCS(X, Y )| n k. Show how this could be used for computing LCS(X, Y ) in time O(nk), where k = n |LCS(X, Y )|. Hint: Assume that the matrix c[1..n, 1..n] is given when all cells are initialized to zero, so you do not need to spend any time initializing them. Show that only O(nk) cells need to be visited.

Explanation / Answer

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

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

2) The value L[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 L[m][n]. Do following for every cell L[i][j]
…..a) If characters (in X and Y) corresponding to L[i][j] are same (Or X[i-1] == Y[j-1]), then include this character as part of LCS.
…..b) Else compare values of L[i-1][j] and L[i][j-1] and go in direction of greater value.

void printLCS(int [M][N]) {
  
   // Start from the right-most-bottom-most corner and
// one by one store characters in lcs[]
int i = m, j = n;
while (i > 0 && j > 0)
{
// If current character in X[] and Y are same, then
// current character is part of LCS
if (X[i-1] == Y[j-1])
{
lcs[index-1] = X[i-1]; // Put current character in result
i--; j--; index--; // reduce values of i, j and index
}

// If not same, then find the larger of two and
// go in the direction of larger value
else if (L[i-1][j] > L[i][j-1])
i--;
else
j--;
}

// Print the lcs
cout << "LCS of " << X << " and " << Y << " is " << lcs;
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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