Question

Q2. Find a longest common subsequence between following strings<br />Stringl- {1,2,3,4,5,6,7,8}<br />String?=<Your Registration Number<br />(Neatly show all the steps and also write the algorithm X Analyze the running time of the<br />given<br />problem).<br />​

Answer 1

Answer:

Printing Longest Common Subsequence

Given two sequences, print the longest subsequence present in both of them.

Examples:

LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.

LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.

We have discussed Longest Common Subsequence (LCS) problem in a previous post. 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 L[][].

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