Consider the following two sequences : X = <B,C, D, C, A, B, C> and π =β¦
2017
Consider the following two sequences :
Β Β Β Β X = <B,C, D, C, A,Β B, C>Β andΒ π = <πΆ,π΄,π·,π΅,πΆ,π΅>
The length of longest common subsequence of X and Y is :
- A.
5
- B.
3
- C.
4
- D.
2
Attempted by 259 students.
Show answer & explanation
Correct answer: C
Answer: 4 β the length of the longest common subsequence.
One example of a longest common subsequence is C, D, B, C.
Positions in X for this subsequence: 2, 3, 6, 7.
Positions in Y for this subsequence: 1, 3, 4, 5.
Sketch of the standard verification method (dynamic programming):
Create a table dp with rows indexed by prefixes of X and columns by prefixes of Y.
Use the recurrence: if the current characters are equal then dp[i][j] = dp[i-1][j-1] + 1; otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Filling the table for X = <B, C, D, C, A, B, C> and Y = <C, A, D, B, C, B> yields dp[7][6] = 4, confirming the longest common subsequence length is 4.
Therefore the correct answer is 4.