Consider two strings \(A = "qpqrr"\) and \(B = "pqprqrp"\). Let \(x\) be the…
2014
Consider two strings \(A = "qpqrr"\) and \(B = "pqprqrp"\). Let \(x\) be the length of the longest common subsequence (not necessarily contiguous) between \(A\) and \(B\) and let \(y\) be the number of such longest common subsequences between \(A\) and \(B\). Then \(x + 10y = \) ______.
Answer: 34 — Compute the longest common subsequence (LCS) length x and the number y of distinct LCSs. All distinct length-4 subsequences of A = "qpqrr" are: "pqrr",…
Attempted by 155 students.
Show answer & explanation
Correct answer: 34
Compute the longest common subsequence (LCS) length x and the number y of distinct LCSs.
All distinct length-4 subsequences of A = "qpqrr" are: "pqrr", "qqrr", "qprr", "qpqr".
Check which appear in B = "pqprqrp":
"pqrr" appears (for example at positions 1,2,4,6 in B).
"qqrr" does not appear as an ordered subsequence in B.
"qprr" appears (for example at positions 2,3,4,6 in B).
"qpqr" appears (for example at positions 2,3,5,6 in B).
Thus there are three distinct LCS strings of length 4, so x = 4 and y = 3.
Answer: 4 + 10×3 = 34
A video solution is available for this question — log in and enroll to watch it.