GATE 2014 CS (CS2) – Question 47
A = “qpqrr”, B = “pqprqrp”. Let x be their longest common subsequence length (not necessarily contiguous), and y the number of such longest common subsequences. Find x + 10y.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 34 to 34
Explanation
Dynamic programming with equal-character diagonal increments gives maximum length4. The distinct length4common subsequences are pqrr,qpqr,qprr; no length5subsequence of A occurs in B. Therefore x=4,y=3 and **x+10y=34**. Different embeddings of the same string are counted once.